DSA

Problem Statement: Pascal’s Triangle II Given an integer rowIndex, return the rowIndex-th row of Pascal’s Triangle. The rowIndex is 0-based, so the first row is row 0. For example: Approach Code Implementations C: #include <stdio.h>#include <stdlib.h>void generateRow(int rowIndex) { int *row = (int *)malloc((rowIndex + 1) * sizeof(int)); row[0] = 1; // First element is always 1 for (int i = 1; i <= rowIndex; i++) { // Update the row in reverse to avoid overwriting previous values for (int j = i; j > 0; j–) { row[j] = row[j] + row[j – 1]; } } // Print the row for (int i = 0; i <= rowIndex; i++) { printf(“%d “, row[i]); } printf(“\n”); free(row);}int main() { int rowIndex = 3; generateRow(rowIndex); // Output: 1 3 3 1 return 0;} C++: #include <iostream>#include <vector>using namespace std;vector<int> getRow(int rowIndex) { vector<int> row(rowIndex + 1, 1); // Initialize the row with 1’s for (int i = 1; i <= rowIndex; i++) { // Update the row in reverse order to prevent overwriting for (int j = i – 1; j > 0; j–) { row[j] += row[j – 1]; } } return row;}int main() { int rowIndex = 3; vector<int> row = getRow(rowIndex); for (int num : row) { cout << num << ” “; } cout << endl; // Output: 1 3 3 1 return 0;} Java: import java.util.ArrayList;import java.util.List;public class PascalsTriangleII { public static List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(); row.add(1); // First element is always 1 for (int i = 1; i <= rowIndex; i++) { // Update the row in reverse order to avoid overwriting for (int j = i – 1; j > 0; j–) { row.set(j, row.get(j) + row.get(j – 1)); } row.add(1); // Add the last element of the row (which is always 1) } return row; } public static void main(String[] args) { int rowIndex = 3; List<Integer> row = getRow(rowIndex); for (int num : row) { System.out.print(num + ” “); } System.out.println(); // Output: 1 3 3 1 }} Python: def getRow(rowIndex): row = [1] # First element is always 1 for i in range(1, rowIndex + 1): # Update the row in reverse order to avoid overwriting for j in range(i – 1, 0, -1): row[j] += row[j – 1] row.append(1) # Add the last element of the row (which is always 1) return row# Example usagerowIndex = 3print(getRow(rowIndex)) # Output: [1, 3, 3, 1] C#: using System;using System.Collections.Generic;class PascalsTriangleII { public static List<int> GetRow(int rowIndex) { var row = new List<int> { 1 }; // First element is always 1 for (int i = 1; i <= rowIndex; i++) { // Update the row in reverse order to prevent overwriting for (int j = i – 1; j > 0; j–) { row[j] += row[j – 1]; } row.Add(1); // Add the last element of the row (which is always 1) } return row; } static void Main() { int rowIndex = 3; var row = GetRow(rowIndex); foreach (var num in row) { Console.Write(num + ” “); } Console.WriteLine(); // Output: 1 3 3 1 }} JavaScript: function getRow(rowIndex) { let row = [1]; // First element is always 1 for (let i = 1; i <= rowIndex; i++) { // Update the row in reverse order to avoid overwriting for (let j = i – 1; j > 0; j–) { row[j] += row[j – 1]; } row.push(1); // Add the last element of the row (which is always 1) } return row;}// Example usagelet rowIndex = 3;console.log(getRow(rowIndex)); // Output: [1, 3, 3, 1] Explanation: For rowIndex = 3, the steps to generate the row [1, 3, 3, 1] are: Time Complexity: Space Complexity: Summary: This solution computes the rowIndex-th row of Pascal’s Triangle directly using an efficient iterative approach, making it more space- and time-efficient than generating the entire triangle.

Problem Statement: Pascal’s Triangle Pascal’s Triangle is a triangular array of binomial coefficients. Each row represents the coefficients of the binomial expansion for increasing powers of (x + y). The triangle starts with a 1 at the top (which is row 0), and each subsequent row contains the binomial coefficients for the expansion of (x + y)^n. Example of Pascal’s Triangle: Row 0: [1]Row 1: [1, 1]Row 2: [1, 2, 1]Row 3: [1, 3, 3, 1]Row 4: [1, 4, 6, 4, 1]Row 5: [1, 5, 10, 10, 5, 1] Task: Given an integer numRows, generate the first numRows of Pascal’s Triangle. Approach Code Implementation in Multiple Languages C: #include <stdio.h>void generate(int numRows) { int triangle[numRows][numRows]; for (int i = 0; i < numRows; i++) { for (int j = 0; j <= i; j++) { if (j == 0 || j == i) triangle[i][j] = 1; else triangle[i][j] = triangle[i – 1][j – 1] + triangle[i – 1][j]; } } // Print the triangle for (int i = 0; i < numRows; i++) { for (int j = 0; j <= i; j++) { printf(“%d “, triangle[i][j]); } printf(“\n”); }}int main() { int numRows = 5; generate(numRows); return 0;} C++: #include <iostream>#include <vector>using namespace std;void generate(int numRows) { vector<vector<int>> triangle(numRows); for (int i = 0; i < numRows; i++) { triangle[i].resize(i + 1, 1); // Resize and fill with 1’s for (int j = 1; j < i; j++) { triangle[i][j] = triangle[i – 1][j – 1] + triangle[i – 1][j]; } } // Print the triangle for (const auto& row : triangle) { for (int num : row) { cout << num << ” “; } cout << endl; }}int main() { int numRows = 5; generate(numRows); return 0;} Java: import java.util.ArrayList;import java.util.List;public class PascalsTriangle { public static List<List<Integer>> generate(int numRows) { List<List<Integer>> triangle = new ArrayList<>(); for (int i = 0; i < numRows; i++) { List<Integer> row = new ArrayList<>(); row.add(1); // First element of each row is 1 // Fill in the middle elements of the row for (int j = 1; j < i; j++) { row.add(triangle.get(i – 1).get(j – 1) + triangle.get(i – 1).get(j)); } if (i > 0) { row.add(1); // Last element of each row is 1 } triangle.add(row); } return triangle; } public static void main(String[] args) { int numRows = 5; List<List<Integer>> result = generate(numRows); // Print the triangle for (List<Integer> row : result) { for (int num : row) { System.out.print(num + ” “); } System.out.println(); } }} Python: def generate(numRows): triangle = [] for i in range(numRows): row = [1] * (i + 1) # Initialize a row with 1’s for j in range(1, i): row[j] = triangle[i – 1][j – 1] + triangle[i – 1][j] triangle.append(row) return triangle# Example usagenumRows = 5triangle = generate(numRows)# Print the trianglefor row in triangle: print(row) C#: using System;using System.Collections.Generic;class PascalsTriangle { public static List<List<int>> Generate(int numRows) { var triangle = new List<List<int>>(); for (int i = 0; i < numRows; i++) { var row = new List<int>(new int[i + 1]); row[0] = 1; // First element of each row is 1 row[i] = 1; // Last element of each row is 1 for (int j = 1; j < i; j++) { row[j] = triangle[i – 1][j – 1] + triangle[i – 1][j]; } triangle.Add(row); } return triangle; } static void Main() { int numRows = 5; var triangle = Generate(numRows); // Print the triangle foreach (var row in triangle) { foreach (var num in row) { Console.Write(num + ” “); } Console.WriteLine(); } }} JavaScript: function generate(numRows) { let triangle = []; for (let i = 0; i < numRows; i++) { let row = Array(i + 1).fill(1); // Initialize a row with 1’s // Fill in the middle elements of the row for (let j = 1; j < i; j++) { row[j] = triangle[i – 1][j – 1] + triangle[i – 1][j]; } triangle.push(row); } return triangle;}// Example usagelet numRows = 5;let triangle = generate(numRows);// Print the triangletriangle.forEach(row => { console.log(row.join(‘ ‘));}); Explanation of Output: For numRows = 5, the generated Pascal’s Triangle will look like: 11 11 2 11 3 3 11 4 6 4 1 Each element is computed as the sum of the two elements directly above it. For instance, the element 3 in the 4th row is the sum of the two 3s from the 3rd row, and so on. Summary:

Problem Statement: Distinct Subsequences Given two strings s and t, return the number of distinct subsequences of s that equals t. A subsequence of a string is a new string formed from the original string by deleting some (or no) characters without changing the relative order of the remaining characters. For example, if s = “rabbbit” and t = “rabbit”, the number of distinct subsequences is 3. Approach This problem can be solved using Dynamic Programming (DP). The idea is to maintain a 2D table dp[i][j] where: dp[i][j] stores the number of ways to form the first j characters of t from the first i characters of s. Recurrence Relation: Base Case: Time Complexity: Space Complexity: Code in Multiple Languages C: #include <stdio.h>#include <string.h>int numDistinct(char* s, char* t) { int m = strlen(s); int n = strlen(t); int dp[m + 1][n + 1]; // Base case initialization for (int i = 0; i <= m; i++) { dp[i][0] = 1; // An empty string t can be formed from any prefix of s } for (int j = 1; j <= n; j++) { dp[0][j] = 0; // An empty string s cannot form a non-empty t } // Fill the dp table for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i – 1] == t[j – 1]) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n];}int main() { char s[] = “rabbbit”; char t[] = “rabbit”; printf(“%d\n”, numDistinct(s, t)); // Output: 3 return 0;} C++: #include <iostream>#include <vector>#include <string>using namespace std;int numDistinct(string s, string t) { int m = s.size(), n = t.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i <= m; i++) { dp[i][0] = 1; // An empty t can be formed from any prefix of s } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i – 1] == t[j – 1]) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n];}int main() { string s = “rabbbit”, t = “rabbit”; cout << numDistinct(s, t) << endl; // Output: 3 return 0;} Java: public class DistinctSubsequences { public static int numDistinct(String s, String t) { int m = s.length(), n = t.length(); int[][] dp = new int[m + 1][n + 1]; // Initialize base case for (int i = 0; i <= m; i++) { dp[i][0] = 1; // An empty string t can be formed from any prefix of s } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s.charAt(i – 1) == t.charAt(j – 1)) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n]; } public static void main(String[] args) { String s = “rabbbit”, t = “rabbit”; System.out.println(numDistinct(s, t)); // Output: 3 }} Python: def numDistinct(s: str, t: str) -> int: m, n = len(s), len(t) dp = [[0] * (n + 1) for _ in range(m + 1)] # Base case for i in range(m + 1): dp[i][0] = 1 # An empty t can be formed from any prefix of s for i in range(1, m + 1): for j in range(1, n + 1): if s[i – 1] == t[j – 1]: dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j] else: dp[i][j] = dp[i – 1][j] return dp[m][n]# Example usages = “rabbbit”t = “rabbit”print(numDistinct(s, t)) # Output: 3 C#: using System;class Program { public static int NumDistinct(string s, string t) { int m = s.Length, n = t.Length; int[,] dp = new int[m + 1, n + 1]; // Initialize base case for (int i = 0; i <= m; i++) { dp[i, 0] = 1; // An empty t can be formed from any prefix of s } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s[i – 1] == t[j – 1]) { dp[i, j] = dp[i – 1, j – 1] + dp[i – 1, j]; } else { dp[i, j] = dp[i – 1, j]; } } } return dp[m, n]; } static void Main() { string s = “rabbbit”; string t = “rabbit”; Console.WriteLine(NumDistinct(s, t)); // Output: 3 }} JavaScript: function numDistinct(s, t) { const m = s.length, n = t.length; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // Base case for (let i = 0; i <= m; i++) { dp[i][0] = 1; // An empty t can be formed from any prefix of s } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (s[i – 1] === t[j – 1]) { dp[i][j] = dp[i – 1][j – 1] + dp[i – 1][j]; } else { dp[i][j] = dp[i – 1][j]; } } } return dp[m][n];}// Example usageconst s = “rabbbit”, t = “rabbit”;console.log(numDistinct(s, t)); // Output: 3 Summary: This solution uses Dynamic Programming to efficiently solve the problem of finding distinct subsequences. The idea is to build a 2D table dp that records how many ways the string t can be formed from any prefix of string s. Each of the implementations in C, C++, Java, Python, C#, and JavaScript follows the same approach with appropriate syntax for the respective language.

Given a singly linked list, check if the linked list has a loop (cycle) or not. A loop means that the last node of the linked list is connected back to a node in the same list. Using HashSet – O(n) Time and O(n) Space: To solve the issue, take the actions listed below: C++ Java Python JS Output true Time complexity: O(n), where n is the number of nodes in the Linked List.Auxiliary Space: O(n), n is the space required to store the value in the hash set.

The recursive relation can be expressed as follows: Check if the term is present in the dictionary using dictSet.count(s.substr(start, end – start)) for each substring s[start..end] where end > start.For any wordBreakHelper(s, dictSet, memo, end) result that is valid:Just add the term if it’s empty.If not, use a space to concatenate the term with the sub-sentence. C++ Java Python JS Output cat sand dog cats and dog

The aim is to return all conceivable ways to break the sentence in individual dictionary words given a dictionary dict[] with a list of non-empty words and a non-empty sequence s.Note: When breaking, a dictionary word may be used more than once. Examples:  Input: s = “catsanddog” , dict = [“cat”, “cats”, “and”, “sand”, “dog”]Output: “cats and dog” “cat sand dog”Explanation: The string is split into above 2 ways, in each way all are valid dictionary words. Input: s = “pineapplepenapple” , dict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]Output: “pine apple pen apple” “pineapple pen apple” “pine applepen apple” Explanation: The string is split into above 3 ways, in each way all are valid dictionary words. How to put the aforementioned concept into practice: C++ Java Python JS Output i like sam sung mobile i like samsung mobile

Determine whether an input string can be divided into a space-separated sequence of dictionary terms given a dictionary of words. For further information, see the examples that follow.This is a well-known Google interview question that is being asked by many other businesses as well. C++ Java Python JS Output Yes Yes Yes Yes Yes No

How to use a random pointer and next to clone a linked list: C++ Java Python C# JS Output 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)

Each node in a linked list of size N contains two links: a random pointer to any random node in the list and a next pointer to the next node. Making a copy of this linked list is the work at hand. Table of Content How to use a random pointer and next to clone a linked list: To store the new nodes that correspond to their original nodes, create a hash table with the value mp.For each node in the original linked list, say curr,mp[curr] = new Node() creates a new node that corresponds to curr and pushes it into a hash table.To update the next and random pointer of every new node, iterate through the original linked list once more: mp[curr]->next = mp[curr->next] and mp[curr]->random = mp[curr->random].Return the cloned linked list’s head, mp[head].The application of the aforementioned strategy is seen below: C++14 Java Python JS Output Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Time Complexity: O(2n), as we are traversing the linked list twice. Auxiliary Space: O(2n), extra O(n) space as we are using a hash table to store the new nodes.

It has previously been detailed how to clone a Binary Tree and LinkedList using random pointers. The concept of graph copying is essentially the same. The goal is to perform a BFS traversal of the graph and create a clone node—a replica of the original node—while visiting a node. A clone node is already present if a node that has already been visited is encountered. How can I monitor the nodes that have been visited or cloned? Maintaining all of the previously generated nodes requires a hash map or map. Important stores: The original node’s address or reference Value shops: Address/Reference of the Cloned Node A duplicate of every node in the graph has been created. How are clone nodes connected? Visit all of the neighboring nodes for u, find the corresponding clone node for each neighbor (or create one if none exists), and then push into the neighboring vector of the cloneNodeU node. This process is done while visiting the neighboring vertices of a node u to obtain the corresponding cloned node for u, which we’ll call cloneNodeU. How can I tell whether the cloned graph is accurate? Before and after the graph is cloned, perform a BFS traversal. In BFS traversal, show a node’s value in addition to its address or reference. Examine the node order; if the values are the same but the address or reference varies between the two traversals, the cloned graph is accurate. C++ Java Python3 Javascript Output BFS Traversal before cloning Value of Node 1 Address of Node 0x1b6ce70 Value of Node 2 Address of Node 0x1b6cea0 Value of Node 4 Address of Node 0x1b6cf00 Value of Node 3 Address of Node 0x1b6ced0 BFS Traversal after cloning Value of Node 1 Address of Node 0x1b6e5a0 Value of Node 2 Address of Node 0x1b6e5d0 Value of Node 4 Address of Node 0x1b6e620 Value of Node 3 Address of Node 0x1b6e670