SkylineWebZ

Problem Statement: Best Time to Buy and Sell Stock III You are given an integer array prices where prices[i] is the price of a given stock on the i-th day. You can complete at most two transactions. In other words, you can make at most two buy-sell pairs. Each transaction consists of buying one stock and then selling it. You cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Return the maximum profit you can achieve. Example: Approach To solve this problem, we can use Dynamic Programming (DP) to track the maximum profit we can make with at most two transactions. The key idea is to break the problem into two subproblems: Dynamic Programming Approach: Steps: Code Implementation C: #include <stdio.h>int maxProfit(int* prices, int pricesSize) { if (pricesSize == 0) return 0; int first[pricesSize], second[pricesSize]; int minPrice = prices[0]; first[0] = 0; // no profit on the first day // Calculate maximum profit with at most one transaction up to day i for (int i = 1; i < pricesSize; i++) { first[i] = (prices[i] – minPrice > first[i – 1]) ? prices[i] – minPrice : first[i – 1]; minPrice = (prices[i] < minPrice) ? prices[i] : minPrice; } int maxPrice = prices[pricesSize – 1]; second[pricesSize – 1] = 0; // no profit on the last day // Calculate maximum profit with at most one transaction from day i to end for (int i = pricesSize – 2; i >= 0; i–) { second[i] = (maxPrice – prices[i] > second[i + 1]) ? maxPrice – prices[i] : second[i + 1]; maxPrice = (prices[i] > maxPrice) ? prices[i] : maxPrice; } int maxProfit = 0; for (int i = 0; i < pricesSize; i++) { maxProfit = (first[i] + second[i] > maxProfit) ? first[i] + second[i] : maxProfit; } return maxProfit;}int main() { int prices[] = {3,2,6,5,0,3}; int pricesSize = sizeof(prices) / sizeof(prices[0]); printf(“Max profit: %d\n”, maxProfit(prices, pricesSize)); // Output: 7 return 0;} C++: #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxProfit(vector<int>& prices) { int n = prices.size(); if (n == 0) return 0; vector<int> first(n, 0), second(n, 0); int minPrice = prices[0]; // Calculate maximum profit for the first transaction up to each day for (int i = 1; i < n; i++) { first[i] = max(first[i – 1], prices[i] – minPrice); minPrice = min(minPrice, prices[i]); } int maxPrice = prices[n – 1]; // Calculate maximum profit for the second transaction from each day for (int i = n – 2; i >= 0; i–) { second[i] = max(second[i + 1], maxPrice – prices[i]); maxPrice = max(maxPrice, prices[i]); } int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = max(maxProfit, first[i] + second[i]); } return maxProfit;}int main() { vector<int> prices = {3,2,6,5,0,3}; cout << “Max profit: ” << maxProfit(prices) << endl; // Output: 7 return 0;} Java: public class BestTimeToBuyAndSellStockIII { public static int maxProfit(int[] prices) { int n = prices.length; if (n == 0) return 0; int[] first = new int[n]; int[] second = new int[n]; // First transaction: calculate max profit up to each day int minPrice = prices[0]; for (int i = 1; i < n; i++) { first[i] = Math.max(first[i – 1], prices[i] – minPrice); minPrice = Math.min(minPrice, prices[i]); } // Second transaction: calculate max profit from each day to the end int maxPrice = prices[n – 1]; for (int i = n – 2; i >= 0; i–) { second[i] = Math.max(second[i + 1], maxPrice – prices[i]); maxPrice = Math.max(maxPrice, prices[i]); } // Max profit by combining both transactions int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.max(maxProfit, first[i] + second[i]); } return maxProfit; } public static void main(String[] args) { int[] prices = {3, 2, 6, 5, 0, 3}; System.out.println(“Max profit: ” + maxProfit(prices)); // Output: 7 }} Python: def maxProfit(prices): n = len(prices) if n == 0: return 0 first = [0] * n second = [0] * n # First transaction: calculate max profit up to each day min_price = prices[0] for i in range(1, n): first[i] = max(first[i – 1], prices[i] – min_price) min_price = min(min_price, prices[i]) # Second transaction: calculate max profit from each day to the end max_price = prices[-1] for i in range(n – 2, -1, -1): second[i] = max(second[i + 1], max_price – prices[i]) max_price = max(max_price, prices[i]) # Max profit by combining both transactions max_profit = 0 for i in range(n): max_profit = max(max_profit, first[i] + second[i]) return max_profit# Example usageprices = [3, 2, 6, 5, 0, 3]print(“Max profit:”, maxProfit(prices)) # Output: 7 C#: using System;public class BestTimeToBuyAndSellStockIII { public static int MaxProfit(int[] prices) { int n = prices.Length; if (n == 0) return 0; int[] first = new int[n]; int[] second = new int[n]; // First transaction: calculate max profit up to each day int minPrice = prices[0]; for (int i = 1; i < n; i++) { first[i] = Math.Max(first[i – 1], prices[i] – minPrice); minPrice = Math.Min(minPrice, prices[i]); } // Second transaction: calculate max profit from each day to the end int maxPrice = prices[n – 1]; for (int i = n – 2; i >= 0; i–) { second[i] = Math.Max(second[i + 1], maxPrice – prices[i]); maxPrice = Math.Max(maxPrice, prices[i]); } // Max profit by combining both transactions int maxProfit = 0; for (int i = 0; i < n; i++) { maxProfit = Math.Max(maxProfit, first[i] + second[i]); } return maxProfit; } static void Main() { int[] prices = {3, 2, 6, 5, 0, 3}; Console.WriteLine(“Max profit: ” + MaxProfit(prices)); // Output: 7 }} JavaScript: function maxProfit(prices) { const n = prices.length; if (n === 0) return 0; let first = Array(n).fill(0); let second = Array(n).fill(0); // First transaction: calculate max profit up to each day let minPrice = prices[0]; for (let i = 1; i < n; i++) { first[i] = Math.max(first[i – 1], prices[i] – minPrice); minPrice = Math.min(minPrice, prices[i]); } // Second transaction: calculate max profit from each

Problem Statement: Best Time to Buy and Sell Stock II You are given an integer array prices where prices[i] is the price of a given stock on the i-th day. You can buy and sell the stock as many times as you like (i.e., multiple transactions are allowed). However, you must sell the stock before you buy again. Return the maximum profit you can achieve. Example: Approach In this case, multiple transactions are allowed. A straightforward solution is to buy and sell the stock whenever there is a price increase, since each increase provides an opportunity for profit. Code Implementation C: #include <stdio.h>int maxProfit(int* prices, int pricesSize) { int max_profit = 0; for (int i = 1; i < pricesSize; i++) { if (prices[i] > prices[i – 1]) { max_profit += prices[i] – prices[i – 1]; // add the profit from price increase } } return max_profit;}int main() { int prices[] = {7, 1, 5, 3, 6, 4}; int pricesSize = sizeof(prices) / sizeof(prices[0]); printf(“Max profit: %d\n”, maxProfit(prices, pricesSize)); // Output: 7 return 0;} C++: #include <iostream>#include <vector>using namespace std;int maxProfit(vector<int>& prices) { int max_profit = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] > prices[i – 1]) { max_profit += prices[i] – prices[i – 1]; // add the profit from price increase } } return max_profit;}int main() { vector<int> prices = {7, 1, 5, 3, 6, 4}; cout << “Max profit: ” << maxProfit(prices) << endl; // Output: 7 return 0;} Java: public class BestTimeToBuyAndSellStockII { public static int maxProfit(int[] prices) { int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i – 1]) { maxProfit += prices[i] – prices[i – 1]; // add the profit from price increase } } return maxProfit; } public static void main(String[] args) { int[] prices = {7, 1, 5, 3, 6, 4}; System.out.println(“Max profit: ” + maxProfit(prices)); // Output: 7 }} Python: def maxProfit(prices): max_profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i – 1]: max_profit += prices[i] – prices[i – 1] # add the profit from price increase return max_profit# Example usageprices = [7, 1, 5, 3, 6, 4]print(“Max profit:”, maxProfit(prices)) # Output: 7 C#: using System;public class BestTimeToBuyAndSellStockII { public static int MaxProfit(int[] prices) { int maxProfit = 0; for (int i = 1; i < prices.Length; i++) { if (prices[i] > prices[i – 1]) { maxProfit += prices[i] – prices[i – 1]; // add the profit from price increase } } return maxProfit; } static void Main() { int[] prices = {7, 1, 5, 3, 6, 4}; Console.WriteLine(“Max profit: ” + MaxProfit(prices)); // Output: 7 }} JavaScript: function maxProfit(prices) { let maxProfit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i – 1]) { maxProfit += prices[i] – prices[i – 1]; // add the profit from price increase } } return maxProfit;}// Example usagelet prices = [7, 1, 5, 3, 6, 4];console.log(“Max profit:”, maxProfit(prices)); // Output: 7 Explanation: Summary: This problem can be efficiently solved using a greedy approach, where we accumulate profits from each price increase. This approach runs in O(n) time and uses O(1) space, making it optimal for this problem. It works well when multiple transactions are allowed, as we can capture all upward price movements.

Problem Statement: Best Time to Buy and Sell Stock You are given an array of integers where each element represents the price of a stock on a given day. You need to find the maximum profit you can achieve by buying and selling the stock exactly once. You can assume that you can only make one buy and one sell. The buying must happen before the selling. Example: Approach Steps: Code Implementations C: #include <stdio.h>int maxProfit(int* prices, int pricesSize) { int min_price = prices[0]; int max_profit = 0; for (int i = 1; i < pricesSize; i++) { if (prices[i] < min_price) { min_price = prices[i]; // update min price } else { int profit = prices[i] – min_price; if (profit > max_profit) { max_profit = profit; // update max profit } } } return max_profit;}int main() { int prices[] = {7, 1, 5, 3, 6, 4}; int pricesSize = sizeof(prices) / sizeof(prices[0]); printf(“Max profit: %d\n”, maxProfit(prices, pricesSize)); // Output: 5 return 0;} C++: #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxProfit(vector<int>& prices) { int min_price = prices[0]; int max_profit = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] < min_price) { min_price = prices[i]; // update min price } else { int profit = prices[i] – min_price; max_profit = max(max_profit, profit); // update max profit } } return max_profit;}int main() { vector<int> prices = {7, 1, 5, 3, 6, 4}; cout << “Max profit: ” << maxProfit(prices) << endl; // Output: 5 return 0;} Java: public class BestTimeToBuyAndSellStock { public static int maxProfit(int[] prices) { int minPrice = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; // update min price } else { int profit = prices[i] – minPrice; maxProfit = Math.max(maxProfit, profit); // update max profit } } return maxProfit; } public static void main(String[] args) { int[] prices = {7, 1, 5, 3, 6, 4}; System.out.println(“Max profit: ” + maxProfit(prices)); // Output: 5 }} Python: def maxProfit(prices): min_price = prices[0] max_profit = 0 for price in prices[1:]: if price < min_price: min_price = price # update min price else: profit = price – min_price max_profit = max(max_profit, profit) # update max profit return max_profit# Example usageprices = [7, 1, 5, 3, 6, 4]print(“Max profit:”, maxProfit(prices)) # Output: 5 C#: using System;public class BestTimeToBuyAndSellStock { public static int MaxProfit(int[] prices) { int minPrice = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.Length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; // update min price } else { int profit = prices[i] – minPrice; maxProfit = Math.Max(maxProfit, profit); // update max profit } } return maxProfit; } static void Main() { int[] prices = {7, 1, 5, 3, 6, 4}; Console.WriteLine(“Max profit: ” + MaxProfit(prices)); // Output: 5 }} JavaScript: function maxProfit(prices) { let minPrice = prices[0]; let maxProfit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i]; // update min price } else { let profit = prices[i] – minPrice; maxProfit = Math.max(maxProfit, profit); // update max profit } } return maxProfit;}// Example usagelet prices = [7, 1, 5, 3, 6, 4];console.log(“Max profit:”, maxProfit(prices)); // Output: 5 Explanation of Approach: Time Complexity: Space Complexity: Edge Cases: Summary: This problem can be efficiently solved using a greedy approach, tracking the minimum price and calculating the potential profit at each step. The solution runs in linear time and constant space, making it highly optimal.

Problem Statement: Triangle Given a triangle represented as a 2D array of integers, where each row in the triangle contains one more number than the previous row, find the minimum path sum from the top to the bottom. Each step you may move to an adjacent number in the row directly below, i.e., from triangle[i][j] to triangle[i+1][j] or triangle[i+1][j+1]. For example: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Approach This problem can be solved using Dynamic Programming. The key idea is to start from the bottom of the triangle and work upwards, updating each element in the triangle with the minimum path sum from that element to the bottom. Example For the triangle: 2 3 4 6 5 7 4 1 8 3 We start from the bottom: Thus, the minimum path sum is 11. Code Implementations C: #include <stdio.h>int minimumTotal(int** triangle, int numRows) { // Start from the second last row and work upwards for (int row = numRows – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += (triangle[row + 1][col] < triangle[row + 1][col + 1]) ? triangle[row + 1][col] : triangle[row + 1][col + 1]; } } // The top element now contains the minimum path sum return triangle[0][0];}int main() { int numRows = 4; int triangle[4][4] = { {2, 0, 0, 0}, {3, 4, 0, 0}, {6, 5, 7, 0}, {4, 1, 8, 3} }; // Converting static 2D array to dynamic 2D array for passing to function int* trianglePointers[4]; for (int i = 0; i < 4; i++) { trianglePointers[i] = triangle[i]; } printf(“Minimum Total: %d\n”, minimumTotal(trianglePointers, numRows)); // Output: 11 return 0;} C++: #include <iostream>#include <vector>using namespace std;int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); // Start from the second last row and work upwards for (int row = n – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]); } } // The top element now contains the minimum path sum return triangle[0][0];}int main() { vector<vector<int>> triangle = { {2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3} }; cout << “Minimum Total: ” << minimumTotal(triangle) << endl; // Output: 11 return 0;} Java: import java.util.List;import java.util.ArrayList;public class Triangle { public static int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); // Start from the second last row and work upwards for (int row = n – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it int minPathSum = Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1)); triangle.get(row).set(col, triangle.get(row).get(col) + minPathSum); } } // The top element now contains the minimum path sum return triangle.get(0).get(0); } public static void main(String[] args) { List<List<Integer>> triangle = new ArrayList<>(); triangle.add(List.of(2)); triangle.add(List.of(3, 4)); triangle.add(List.of(6, 5, 7)); triangle.add(List.of(4, 1, 8, 3)); System.out.println(“Minimum Total: ” + minimumTotal(triangle)); // Output: 11 }} Python: def minimumTotal(triangle): n = len(triangle) # Start from the second last row and work upwards for row in range(n – 2, -1, -1): for col in range(row + 1): # Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]) # The top element now contains the minimum path sum return triangle[0][0]# Example usagetriangle = [ [2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]print(“Minimum Total:”, minimumTotal(triangle)) # Output: 11 C#: using System;using System.Collections.Generic;class Triangle { public static int MinimumTotal(List<List<int>> triangle) { int n = triangle.Count; // Start from the second last row and work upwards for (int row = n – 2; row >= 0; row–) { for (int col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it int minPathSum = Math.Min(triangle[row + 1][col], triangle[row + 1][col + 1]); triangle[row][col] += minPathSum; } } // The top element now contains the minimum path sum return triangle[0][0]; } static void Main() { var triangle = new List<List<int>> { new List<int> { 2 }, new List<int> { 3, 4 }, new List<int> { 6, 5, 7 }, new List<int> { 4, 1, 8, 3 } }; Console.WriteLine(“Minimum Total: ” + MinimumTotal(triangle)); // Output: 11 }} JavaScript: function minimumTotal(triangle) { const n = triangle.length; // Start from the second last row and work upwards for (let row = n – 2; row >= 0; row–) { for (let col = 0; col <= row; col++) { // Update the current element by adding the minimum of the two adjacent elements below it triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]); } } // The top element now contains the minimum path sum return triangle[0][0];}// Example usageconst triangle = [ [2], [3, 4], [6, 5, 7], [4, 1, 8, 3]];console.log(“Minimum Total:”, minimumTotal(triangle)); // Output: 11 Explanation: Time Complexity: Space Complexity: Summary: The problem of finding the minimum path sum in a triangle can be efficiently solved using dynamic programming with a bottom-up approach. This approach minimizes the space complexity by modifying the triangle in place.

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.