SkylineWebZ

Examples:  Input : 9Output : IXInput : 40Output : XLInput : 1904Output : MCMIV Following is the list of Roman symbols which include subtractive cases also: SYMBOL VALUEI 1IV 4V 5IX 9X 10XL 40L 50XC 90C 100CD 400D 500CM 900 M 1000 The plan is to separately convert the tens, hundreds, thousands of sites of the specified number. There is no matching Roman numeral symbol if the digit is zero. Because these digits use subtractive notation, the conversion of digits 4’s and 9’s is somewhat different from other digits. Method for Roman numeral conversion from decimal numberComparing provided number with base values in the sequence 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1, The first base value—largest base value—will be either exactly less or equal to the specified integer.Divide the number by its highest base value; the corresponding base symbol will be repeated quotient times; the residual will then be the number for next divisions and repetitions. The cycle will be continued until the count runs zero. Example to demonstrate above algorithm:  Convert 3549 to its Roman Numerals Output:  MMMDXLIX Explanation: First step: First number = 3549Since 3549 > 1000; first base value will be 1000 initially.Get 3549/1000 divided. Remainder =549; quotient = 3. Three times will be the equivalent sign M repeated.We list the Result value in the second list.Now remainder is not equal to zero hence we call the method once more. Two steps Number now is 549; maximum base value will be 500; 1000 > 549 >= 500.Split 549/500. Remainder: 49; quotient: 1. Once, the matching symbol D will be repeated to stop the loop.We list the Result value in the second list.Now remainder is not equal to zero hence we call the method once more.The third step Number now is 49; maximum base value is 40; 50 > 49 >= 40.Sort 49/40. Quotient is one; remainder is nine. Once, the matching symbol XL will be repeated to stop the loop.We list the Result value in the second list.Now remainder is not equal to zero hence we call the method once more.Step Four Now, number is 9.List l contains number 9; so, we straight get the value from dictionary dict and set Remainder=0 and finish the loop.Remainder= 0. We shall not call the method once more since the related symbol IX will be repeated once and the remaining value is 0.Step five At last, we align with the second list values.The result came MMMDXLIX.The above method is applied following here: C++ Java Python C# Output MMMDXLIX Time Complexity: O(N), where N is the length of ans string that stores the conversion.Auxiliary Space: O(N)

Print all conceivable letter combinations the integers could represent from an integer array with digits from [0, 9]. Following a mapping of digits to letters, much as on phone buttons. 0 and 1 do not map to any letters, by note. The picture below shows every mapping point: Example:  Input: arr[] = {2, 3} Output: ad ae af bd be bf cd ce cf Input: arr[] = {9} Output: w x y z  Simple Answer: RecursiveThe concept is basic; we examine each digit one by one. We progressively add all mappings of the remaining digits after obtaining all mappings of the current digit. Taking index as an argument, we create a recursive function letter combinations). We one by one map all instances of current characters to res and recursively call for the next index. C++ C Java Python JS Output ad ae af bd be bf cd ce cf Read More: Efficient Solution – Using Queue

Problem Statement: Edit Distance Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations available: Example 1: Input: word1 = “horse”, word2 = “ros” Output: 3 Explanation: The minimum number of operations required to convert “horse” to “ros” is: Thus, the answer is 3. Example 2: Input: word1 = “intention”, word2 = “execution” Output: 5 Explanation: The minimum number of operations required to convert “intention” to “execution” is: Thus, the answer is 5. Approach: This problem can be solved using Dynamic Programming (DP), where we build a table dp[i][j] to store the minimum edit distance between the first i characters of word1 and the first j characters of word2. DP Table Definition: Recurrence Relation: Time and Space Complexity: Code Implementations in Different Languages: 1. C Language (DP Approach): #include <stdio.h>#include <string.h>int min(int a, int b, int c) { if (a <= b && a <= c) return a; if (b <= a && b <= c) return b; return c;}int minDistance(char* word1, char* word2) { int m = strlen(word1), n = strlen(word2); int dp[m + 1][n + 1]; // Initialize base cases for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; // Fill the dp table for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i – 1] == word2[j – 1]) { dp[i][j] = dp[i – 1][j – 1]; } else { dp[i][j] = min(dp[i – 1][j – 1], dp[i][j – 1], dp[i – 1][j]) + 1; } } } return dp[m][n];}int main() { char word1[] = “horse”; char word2[] = “ros”; printf(“Edit Distance: %d\n”, minDistance(word1, word2)); // Output: 3 return 0;} 2. C++ Language (DP Approach): #include <iostream>#include <vector>#include <string>using namespace std;int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // Initialize base cases for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; // Fill the dp table for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i – 1] == word2[j – 1]) { dp[i][j] = dp[i – 1][j – 1]; } else { dp[i][j] = min({dp[i – 1][j – 1], dp[i][j – 1], dp[i – 1][j]}) + 1; } } } return dp[m][n];}int main() { string word1 = “horse”, word2 = “ros”; cout << “Edit Distance: ” << minDistance(word1, word2) << endl; // Output: 3 return 0;} 3. Java (DP Approach): public class EditDistance { public static int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m + 1][n + 1]; // Initialize base cases for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; // Fill the dp table for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1.charAt(i – 1) == word2.charAt(j – 1)) { dp[i][j] = dp[i – 1][j – 1]; } else { dp[i][j] = Math.min(dp[i – 1][j – 1], Math.min(dp[i][j – 1], dp[i – 1][j])) + 1; } } } return dp[m][n]; } public static void main(String[] args) { String word1 = “horse”, word2 = “ros”; System.out.println(“Edit Distance: ” + minDistance(word1, word2)); // Output: 3 }} 4. Python (DP Approach): def minDistance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] # Initialize base cases for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j # Fill the dp table for i in range(1, m + 1): for j in range(1, n + 1): if word1[i – 1] == word2[j – 1]: dp[i][j] = dp[i – 1][j – 1] else: dp[i][j] = min(dp[i – 1][j – 1], min(dp[i][j – 1], dp[i – 1][j])) + 1 return dp[m][n]# Test caseword1 = “horse”word2 = “ros”print(f”Edit Distance: {minDistance(word1, word2)}”) # Output: 3 5. C# (DP Approach): using System;class Program { public static int MinDistance(string word1, string word2) { int m = word1.Length, n = word2.Length; int[,] dp = new int[m + 1, n + 1]; // Initialize base cases for (int i = 0; i <= m; i++) dp[i, 0] = i; for (int j = 0; j <= n; j++) dp[0, j] = j; // Fill the dp table for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i – 1] == word2[j – 1]) { dp[i, j] = dp[i – 1, j – 1]; } else { dp[i, j] = Math.Min(dp[i – 1, j – 1], Math.Min(dp[i, j – 1], dp[i – 1, j])) + 1; } } } return dp[m, n]; } static void Main() { string word1 = “horse”, word2 = “ros”; Console.WriteLine($”Edit Distance: {MinDistance(word1, word2)}”); // Output: 3 }} 6. JavaScript (DP Approach): function minDistance(word1, word2) { let m = word1.length, n = word2.length; let dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0)); // Initialize base cases for (let i = 0; i <= m; i++) dp[i][0] = i; for (let j = 0; j <= n; j++) dp[0][j] = j; // Fill the dp table for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (word1[i – 1] === word2[j – 1]) { dp[i][j] = dp[i – 1][j – 1]; } else { dp[i][j] = Math.min(dp[i – 1][j – 1], Math.min(dp[i][j – 1], dp[i – 1][j])) + 1; } } } return dp[m][n];}// Test caselet word1 = “horse”, word2 = “ros”;console.log(`Edit Distance: ${minDistance(word1, word2)}`); // Output: 3 Complexity Analysis: Time Complexity: Space

Problem Statement: Climbing Stairs You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 step or 2 steps. In how many distinct ways can you reach the top? Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to reach the top: Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to reach the top: Approach: The problem is a variation of the Fibonacci sequence, where each step can be reached from either the previous step (taking 1 step) or the step before that (taking 2 steps). Let’s define dp[i] as the number of distinct ways to reach the i-th step. Recurrence Relation: To reach step i, you can either: Thus, the recurrence relation is:dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]dp[i]=dp[i−1]+dp[i−2] Base Cases: Final Answer: The answer will be dp[n], where n is the number of steps. Time and Space Complexity: Code Implementations in Different Languages: 1. C Language (DP Approach): #include <stdio.h>int climbStairs(int n) { if (n == 1) return 1; int prev2 = 1, prev1 = 1; int current; for (int i = 2; i <= n; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1;}int main() { int n = 3; printf(“Ways to climb %d stairs: %d\n”, n, climbStairs(n)); // Output: 3 return 0;} 2. C++ Language (DP Approach): #include <iostream>using namespace std;int climbStairs(int n) { if (n == 1) return 1; int prev2 = 1, prev1 = 1, current; for (int i = 2; i <= n; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1;}int main() { int n = 3; cout << “Ways to climb ” << n << ” stairs: ” << climbStairs(n) << endl; // Output: 3 return 0;} 3. Java (DP Approach): public class ClimbingStairs { public static int climbStairs(int n) { if (n == 1) return 1; int prev2 = 1, prev1 = 1, current; for (int i = 2; i <= n; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; } public static void main(String[] args) { int n = 3; System.out.println(“Ways to climb ” + n + ” stairs: ” + climbStairs(n)); // Output: 3 }} 4. Python (DP Approach): def climbStairs(n): if n == 1: return 1 prev2, prev1 = 1, 1 for i in range(2, n + 1): current = prev1 + prev2 prev2 = prev1 prev1 = current return prev1# Test casen = 3print(f”Ways to climb {n} stairs: {climbStairs(n)}”) # Output: 3 5. C# (DP Approach): using System;class Program { public static int ClimbStairs(int n) { if (n == 1) return 1; int prev2 = 1, prev1 = 1, current; for (int i = 2; i <= n; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; } static void Main() { int n = 3; Console.WriteLine($”Ways to climb {n} stairs: {ClimbStairs(n)}”); // Output: 3 }} 6. JavaScript (DP Approach): function climbStairs(n) { if (n === 1) return 1; let prev2 = 1, prev1 = 1, current; for (let i = 2; i <= n; i++) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1;}// Test caseconst n = 3;console.log(`Ways to climb ${n} stairs: ${climbStairs(n)}`); // Output: 3 Complexity Analysis: Time Complexity: Space Complexity: Conclusion: The Climbing Stairs problem can be efficiently solved using dynamic programming. By iterating over the steps and using the recurrence relation, we can calculate the number of ways to reach the top in linear time, with constant space complexity.

Problem Statement: Minimum Path Sum You are given a m x n grid filled with non-negative integers. You need to find a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1), which minimizes the sum of the numbers along the path. You can only move right or down at any point in time. Return the minimum path sum. Example 1: Input: grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1]] Output: 7 Explanation: The path to the minimum sum is: 1 → 3 → 1 → 1 → 1, which sums to 7. Example 2: Input: grid = [ [1, 2, 3], [4, 5, 6]] Output: 12 Explanation: The path to the minimum sum is: 1 → 2 → 3 → 6 which sums to 12. Approach: This problem is a classical Dynamic Programming problem. The goal is to build the solution by incrementally calculating the minimum path sum from the start to the end. Dynamic Programming Approach: Time and Space Complexity: Code Implementations in Different Languages: 1. C Language (DP Approach): #include <stdio.h>int minPathSum(int** grid, int m, int n) { int dp[n]; dp[0] = grid[0][0]; // Fill the first row for (int j = 1; j < n; j++) { dp[j] = dp[j – 1] + grid[0][j]; } // Fill the rest of the grid for (int i = 1; i < m; i++) { dp[0] += grid[i][0]; // Update the first column for (int j = 1; j < n; j++) { dp[j] = grid[i][j] + (dp[j – 1] < dp[j] ? dp[j – 1] : dp[j]); } } return dp[n – 1];}int main() { int m = 3, n = 3; int grid[3][3] = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; int* gridPtr[3] = {grid[0], grid[1], grid[2]}; printf(“Minimum Path Sum: %d\n”, minPathSum(gridPtr, m, n)); // Output: 7 return 0;} 2. C++ Language (DP Approach): #include <iostream>#include <vector>using namespace std;int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<int> dp(n, 0); dp[0] = grid[0][0]; // Fill the first row for (int j = 1; j < n; j++) { dp[j] = dp[j – 1] + grid[0][j]; } // Fill the rest of the grid for (int i = 1; i < m; i++) { dp[0] += grid[i][0]; // Update the first column for (int j = 1; j < n; j++) { dp[j] = grid[i][j] + min(dp[j – 1], dp[j]); } } return dp[n – 1];}int main() { vector<vector<int>> grid = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; cout << “Minimum Path Sum: ” << minPathSum(grid) << endl; // Output: 7 return 0;} 3. Java (DP Approach): public class MinimumPathSum { public static int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] dp = new int[n]; dp[0] = grid[0][0]; // Fill the first row for (int j = 1; j < n; j++) { dp[j] = dp[j – 1] + grid[0][j]; } // Fill the rest of the grid for (int i = 1; i < m; i++) { dp[0] += grid[i][0]; // Update the first column for (int j = 1; j < n; j++) { dp[j] = grid[i][j] + Math.min(dp[j – 1], dp[j]); } } return dp[n – 1]; } public static void main(String[] args) { int[][] grid = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; System.out.println(“Minimum Path Sum: ” + minPathSum(grid)); // Output: 7 }} 4. Python (DP Approach): def minPathSum(grid): m = len(grid) n = len(grid[0]) dp = [0] * n dp[0] = grid[0][0] # Fill the first row for j in range(1, n): dp[j] = dp[j – 1] + grid[0][j] # Fill the rest of the grid for i in range(1, m): dp[0] += grid[i][0] # Update the first column for j in range(1, n): dp[j] = grid[i][j] + min(dp[j – 1], dp[j]) return dp[-1]# Test casegrid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1]]print(“Minimum Path Sum:”, minPathSum(grid)) # Output: 7 5. C# (DP Approach): using System;class Program { public static int MinPathSum(int[,] grid) { int m = grid.GetLength(0); int n = grid.GetLength(1); int[] dp = new int[n]; dp[0] = grid[0, 0]; // Fill the first row for (int j = 1; j < n; j++) { dp[j] = dp[j – 1] + grid[0, j]; } // Fill the rest of the grid for (int i = 1; i < m; i++) { dp[0] += grid[i, 0]; // Update the first column for (int j = 1; j < n; j++) { dp[j] = grid[i, j] + Math.Min(dp[j – 1], dp[j]); } } return dp[n – 1]; } static void Main() { int[,] grid = { {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }; Console.WriteLine(“Minimum Path Sum: ” + MinPathSum(grid)); // Output: 7 }} 6. JavaScript (DP Approach): function minPathSum(grid) { let m = grid.length; let n = grid[0].length; let dp = new Array(n).fill(0); dp[0] = grid[0][0]; // Fill the first row for (let j = 1; j < n; j++) { dp[j] = dp[j – 1] + grid[0][j]; } // Fill the rest of the grid for (let i = 1; i < m; i++) { dp[0] += grid[i][0]; // Update the first column for (let j = 1; j < n; j++) { dp[j] = grid[i][j] + Math.min(dp[j – 1], dp[j]); } } return dp[n – 1];}// Test caseconst grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1]];console.log(“Minimum Path Sum:”, minPathSum(grid)); // Output: 7 Complexity Analysis: Time Complexity: Space Complexity: Conclusion: The Minimum Path Sum problem can be efficiently solved using dynamic programming. By calculating the minimum path sum progressively from the top-left corner to the bottom-right corner, we can find the optimal path in O(m * n) time with optimized space usage.

Problem Statement: Unique Paths II You are given a m x n grid, where each cell can either be obstacle (1) or empty (0). You start at the top-left corner (0, 0) and you need to find how many unique paths exist to reach the bottom-right corner (m-1, n-1). You can only move right or down at any point in time. If there is an obstacle at the destination or at the starting point, return 0 as no path is possible. Example 1: Input: grid = [ [0,0,0], [0,1,0], [0,0,0]] Output: 2 Explanation: There are two unique paths: Example 2: Input: grid = [ [0,1], [0,0]] Output: 1 Explanation: There is only one unique path: Down → Right. Approach: This problem is a variation of the Unique Paths problem, but it introduces obstacles into the grid. We will use Dynamic Programming (DP) to solve it. Dynamic Programming Approach: Time and Space Complexity: Code Implementations in Different Languages: 1. C Language (DP Approach): #include <stdio.h>int uniquePathsWithObstacles(int** obstacleGrid, int m, int n) { int dp[n]; // Initialize the first row dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1; for (int j = 1; j < n; j++) { dp[j] = obstacleGrid[0][j] == 1 ? 0 : dp[j-1]; } // Fill in the rest of the grid for (int i = 1; i < m; i++) { dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0]; for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[j] = 0; } else { dp[j] += dp[j-1]; } } } return dp[n-1];}int main() { int m = 3, n = 3; int grid[3][3] = { {0,0,0}, {0,1,0}, {0,0,0} }; int* obstacleGrid[3] = {grid[0], grid[1], grid[2]}; printf(“Unique Paths: %d\n”, uniquePathsWithObstacles(obstacleGrid, m, n)); return 0;} 2. C++ Language (DP Approach): #include <iostream>#include <vector>using namespace std;int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<int> dp(n, 0); // Initialize the first row dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1; for (int j = 1; j < n; j++) { dp[j] = obstacleGrid[0][j] == 1 ? 0 : dp[j-1]; } // Fill in the rest of the grid for (int i = 1; i < m; i++) { dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0]; for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[j] = 0; } else { dp[j] += dp[j-1]; } } } return dp[n-1];}int main() { vector<vector<int>> grid = { {0, 0, 0}, {0, 1, 0}, {0, 0, 0} }; cout << “Unique Paths: ” << uniquePathsWithObstacles(grid) << endl; // Output: 2 return 0;} 3. Java (DP Approach): public class UniquePathsII { public static int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[] dp = new int[n]; dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1; for (int j = 1; j < n; j++) { dp[j] = obstacleGrid[0][j] == 1 ? 0 : dp[j – 1]; } for (int i = 1; i < m; i++) { dp[0] = obstacleGrid[i][0] == 1 ? 0 : dp[0]; for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[j] = 0; } else { dp[j] += dp[j – 1]; } } } return dp[n – 1]; } public static void main(String[] args) { int[][] grid = { {0, 0, 0}, {0, 1, 0}, {0, 0, 0} }; System.out.println(“Unique Paths: ” + uniquePathsWithObstacles(grid)); // Output: 2 }} 4. Python (DP Approach): def uniquePathsWithObstacles(grid): m = len(grid) n = len(grid[0]) dp = [0] * n dp[0] = 1 if grid[0][0] == 0 else 0 for j in range(1, n): dp[j] = 0 if grid[0][j] == 1 else dp[j-1] for i in range(1, m): dp[0] = 0 if grid[i][0] == 1 else dp[0] for j in range(1, n): if grid[i][j] == 1: dp[j] = 0 else: dp[j] += dp[j-1] return dp[-1]# Test casegrid = [ [0, 0, 0], [0, 1, 0], [0, 0, 0]]print(“Unique Paths:”, uniquePathsWithObstacles(grid)) # Output: 2 5. C# (DP Approach): using System;class Program { public static int UniquePathsWithObstacles(int[,] obstacleGrid) { int m = obstacleGrid.GetLength(0); int n = obstacleGrid.GetLength(1); int[] dp = new int[n]; dp[0] = obstacleGrid[0, 0] == 1 ? 0 : 1; for (int j = 1; j < n; j++) { dp[j] = obstacleGrid[0, j] == 1 ? 0 : dp[j – 1]; } for (int i = 1; i < m; i++) { dp[0] = obstacleGrid[i, 0] == 1 ? 0 : dp[0]; for (int j = 1; j < n; j++) { if (obstacleGrid[i, j] == 1) { dp[j] = 0; } else { dp[j] += dp[j – 1]; } } } return dp[n – 1]; } static void Main() { int[,] grid = { {0, 0, 0}, {0, 1, 0}, {0, 0, 0} }; Console.WriteLine(“Unique Paths: ” + UniquePathsWithObstacles(grid)); // Output: 2 }} 6. JavaScript (DP Approach): function uniquePathsWithObstacles(grid) { let m = grid.length; let n = grid[0].length; let dp = new Array(n).fill(0); dp[0] = grid[0][0] === 1 ? 0 : 1; for (let j = 1; j < n; j++) { dp[j] = grid[0][j] === 1 ? 0 : dp[j-1]; } for (let i = 1; i < m; i++) { dp[0] = grid[i][0] === 1 ? 0 : dp[0]; for (let j = 1; j < n; j++) { if (grid[i][j] === 1) { dp[j] = 0; } else { dp[j] += dp[j-1]; } } } return dp[n-1];}// Test caseconst grid = [ [0, 0, 0], [0, 1, 0], [0, 0, 0]];console.log(“Unique Paths:”, uniquePathsWithObstacles(grid)); // Output: 2 Complexity Analysis: Time Complexity: Conclusion: This problem can be efficiently solved using Dynamic Programming by filling up a DP table with the number of unique paths at each cell, while handling obstacles appropriately. The approach ensures that we find the number of unique paths even when obstacles are present in the grid.

Problem Statement: Unique Paths You are given an m x n grid. Starting from the top-left corner, you need to find how many unique paths exist to reach the bottom-right corner. You can only move right or down at any point in time. Write a function to return the number of unique paths. Example 1: Input: m = 3, n = 7 Output: 28 Explanation: There are 28 unique paths to go from the top-left to the bottom-right corner in a 3×7 grid. Example 2: Input: m = 3, n = 2 Output: 3 Explanation: There are 3 unique paths to go from the top-left to the bottom-right corner in a 3×2 grid. Approach: The problem can be solved using Dynamic Programming (DP) or Combinatorics. Approach 1: Dynamic Programming (DP) Approach 2: Combinatorics Code Implementations in Different Languages: 1. C Language (DP Approach): #include <stdio.h>int uniquePaths(int m, int n) { int dp[n]; for (int i = 0; i < n; i++) { dp[i] = 1; // First row, all cells have 1 way (move right only) } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j – 1]; // Sum of top and left cell values } } return dp[n – 1];}int main() { int m = 3, n = 7; printf(“Unique Paths: %d\n”, uniquePaths(m, n)); // Output: 28 return 0;} 2. C++ Language (DP Approach): #include <iostream>#include <vector>using namespace std;int uniquePaths(int m, int n) { vector<int> dp(n, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j – 1]; // Sum of top and left cell values } } return dp[n – 1];}int main() { int m = 3, n = 7; cout << “Unique Paths: ” << uniquePaths(m, n) << endl; // Output: 28 return 0;} 3. Java (DP Approach): public class UniquePaths { public static int uniquePaths(int m, int n) { int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; // First row, all cells have 1 way (move right only) } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j – 1]; // Sum of top and left cell values } } return dp[n – 1]; } public static void main(String[] args) { int m = 3, n = 7; System.out.println(“Unique Paths: ” + uniquePaths(m, n)); // Output: 28 }} 4. Python (DP Approach): def uniquePaths(m, n): dp = [1] * n # First row, all cells have 1 way (move right only) for i in range(1, m): for j in range(1, n): dp[j] += dp[j – 1] # Sum of top and left cell values return dp[-1]# Test casem, n = 3, 7print(“Unique Paths:”, uniquePaths(m, n)) # Output: 28 5. C# (DP Approach): using System;class Program { public static int UniquePaths(int m, int n) { int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; // First row, all cells have 1 way (move right only) } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] += dp[j – 1]; // Sum of top and left cell values } } return dp[n – 1]; } static void Main() { int m = 3, n = 7; Console.WriteLine(“Unique Paths: ” + UniquePaths(m, n)); // Output: 28 }} 6. JavaScript (DP Approach): function uniquePaths(m, n) { let dp = new Array(n).fill(1); // First row, all cells have 1 way (move right only) for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[j] += dp[j – 1]; // Sum of top and left cell values } } return dp[n – 1];}// Test caselet m = 3, n = 7;console.log(“Unique Paths:”, uniquePaths(m, n)); // Output: 28 Approach 2: Combinatorics Using the combinatorics formula, the number of unique paths from the top-left to the bottom-right is given by the binomial coefficient:C(m+n−2,m−1)=(m+n−2)!(m−1)!(n−1)!C(m + n – 2, m – 1) = \frac{(m + n – 2)!}{(m – 1)! (n – 1)!}C(m+n−2,m−1)=(m−1)!(n−1)!(m+n−2)!​ Python Code (Combinatorics Approach): import mathdef uniquePaths(m, n): return math.comb(m + n – 2, m – 1)# Test casem, n = 3, 7print(“Unique Paths (Combinatorics):”, uniquePaths(m, n)) # Output: 28 Complexity Analysis: Dynamic Programming Approach: Combinatorics Approach: Conclusion: The Dynamic Programming approach is a clear and intuitive way to solve the problem with O(m * n) time complexity, and space optimization can make it more efficient. Alternatively, the Combinatorics approach gives an elegant solution with O(min(m, n)) time complexity. Both approaches are suitable depending on the constraints.

The method saves the last indices of already seen characters. Initialized as one character, the concept is to keep a window of different characters. We keep widening the window on the right side till we come upon different personalities. When we see a repeating character, we look for the last index of that repeated character: We adjust the starting index of the current window to last index of repeated character + 1 to eliminate the repeated character if last index of repeated character > starting index of the current window.The window size stays the same if last index of repeated character is already beyond the current window, starting index of the current window indicates that this is so.The biggest window size will be our result after iteratively over every character. C++ C Java Python JS Output 7

Problem Statement: Jump Game You are given an integer array nums. Each element in the array represents your maximum jump length from that position. You start at the first index of the array. Example 1: Input: nums = [2, 3, 1, 1, 4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: nums = [3, 2, 1, 0, 4] Output: false Explanation: You will always arrive at index 3. It’s maximum jump length is 0, which means you can’t move further. Approach: This problem can be solved using a greedy approach. The idea is to keep track of the farthest index that you can reach at each step. If at any point, you are able to reach or surpass the last index, return true. If you can’t reach the last index by the time you process the entire array, return false. Key Ideas: Time Complexity: Algorithm: Code Implementations in Different Languages: 1. C Language: #include <stdio.h>int canJump(int* nums, int numsSize) { int max_reach = 0; for (int i = 0; i < numsSize; i++) { if (i > max_reach) { return 0; // Can’t reach index i } max_reach = (max_reach > i + nums[i]) ? max_reach : i + nums[i]; if (max_reach >= numsSize – 1) { return 1; // Can reach or surpass the last index } } return 0; // Can’t reach the last index}int main() { int nums[] = {2, 3, 1, 1, 4}; int size = sizeof(nums) / sizeof(nums[0]); printf(“Can Jump: %d\n”, canJump(nums, size)); // Output: 1 (true) return 0;} 2. C++ Language: #include <iostream>#include <vector>using namespace std;bool canJump(vector<int>& nums) { int max_reach = 0; for (int i = 0; i < nums.size(); i++) { if (i > max_reach) { return false; // Can’t reach index i } max_reach = max(max_reach, i + nums[i]); if (max_reach >= nums.size() – 1) { return true; // Can reach or surpass the last index } } return false; // Can’t reach the last index}int main() { vector<int> nums = {2, 3, 1, 1, 4}; cout << “Can Jump: ” << canJump(nums) << endl; // Output: 1 (true) return 0;} 3. Java: public class JumpGame { public static boolean canJump(int[] nums) { int maxReach = 0; for (int i = 0; i < nums.length; i++) { if (i > maxReach) { return false; // Can’t reach index i } maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= nums.length – 1) { return true; // Can reach or surpass the last index } } return false; // Can’t reach the last index } public static void main(String[] args) { int[] nums = {2, 3, 1, 1, 4}; System.out.println(“Can Jump: ” + canJump(nums)); // Output: true }} 4. Python: def canJump(nums): max_reach = 0 for i in range(len(nums)): if i > max_reach: return False # Can’t reach index i max_reach = max(max_reach, i + nums[i]) if max_reach >= len(nums) – 1: return True # Can reach or surpass the last index return False # Can’t reach the last index# Test casenums = [2, 3, 1, 1, 4]print(“Can Jump:”, canJump(nums)) # Output: True 5. C#: using System;public class JumpGame { public static bool CanJump(int[] nums) { int maxReach = 0; for (int i = 0; i < nums.Length; i++) { if (i > maxReach) { return false; // Can’t reach index i } maxReach = Math.Max(maxReach, i + nums[i]); if (maxReach >= nums.Length – 1) { return true; // Can reach or surpass the last index } } return false; // Can’t reach the last index } public static void Main() { int[] nums = {2, 3, 1, 1, 4}; Console.WriteLine(“Can Jump: ” + CanJump(nums)); // Output: True }} 6. JavaScript: function canJump(nums) { let maxReach = 0; for (let i = 0; i < nums.length; i++) { if (i > maxReach) { return false; // Can’t reach index i } maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= nums.length – 1) { return true; // Can reach or surpass the last index } } return false; // Can’t reach the last index}// Test caseconst nums = [2, 3, 1, 1, 4];console.log(“Can Jump:”, canJump(nums)); // Output: true Complexity Analysis: Conclusion: This greedy algorithm efficiently solves the Jump Game problem by maintaining the maximum reachable index at each step, ensuring that we can determine if it’s possible to reach the last index with a linear time complexity.

Problem Statement: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Explanation: The subarray with the largest sum is [4, -1, 2, 1], which has a sum of 6. Approach: This problem can be solved using Dynamic Programming. The key idea is to compute the maximum sum subarray that ends at each index and update the global maximum. We will use the following approach: Algorithm: Code Implementations in Different Languages: 1. C Language: #include <stdio.h>int maxSubArray(int* nums, int numsSize) { int current_sum = nums[0], max_sum = nums[0]; for (int i = 1; i < numsSize; i++) { current_sum = (nums[i] > current_sum + nums[i]) ? nums[i] : current_sum + nums[i]; max_sum = (max_sum > current_sum) ? max_sum : current_sum; } return max_sum;}int main() { int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int size = sizeof(nums) / sizeof(nums[0]); printf(“Maximum Subarray Sum: %d\n”, maxSubArray(nums, size)); return 0;} 2. C++ Language: #include <iostream>#include <vector>#include <algorithm>using namespace std;int maxSubArray(vector<int>& nums) { int current_sum = nums[0], max_sum = nums[0]; for (int i = 1; i < nums.size(); i++) { current_sum = max(nums[i], current_sum + nums[i]); max_sum = max(max_sum, current_sum); } return max_sum;}int main() { vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; cout << “Maximum Subarray Sum: ” << maxSubArray(nums) << endl; return 0;} 3. Java: public class Main { public static int maxSubArray(int[] nums) { int currentSum = nums[0], maxSum = nums[0]; for (int i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; } public static void main(String[] args) { int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(“Maximum Subarray Sum: ” + maxSubArray(nums)); }} 4. Python: def maxSubArray(nums): current_sum = nums[0] max_sum = nums[0] for i in range(1, len(nums)): current_sum = max(nums[i], current_sum + nums[i]) max_sum = max(max_sum, current_sum) return max_sum# Test casenums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]print(“Maximum Subarray Sum:”, maxSubArray(nums)) 5. C#: using System;class Program { public static int MaxSubArray(int[] nums) { int currentSum = nums[0], maxSum = nums[0]; for (int i = 1; i < nums.Length; i++) { currentSum = Math.Max(nums[i], currentSum + nums[i]); maxSum = Math.Max(maxSum, currentSum); } return maxSum; } static void Main() { int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; Console.WriteLine(“Maximum Subarray Sum: ” + MaxSubArray(nums)); }} 6. JavaScript: function maxSubArray(nums) { let currentSum = nums[0]; let maxSum = nums[0]; for (let i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum;}// Test caseconst nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];console.log(“Maximum Subarray Sum:”, maxSubArray(nums)); Complexity Analysis: Conclusion: This problem is efficiently solvable using Dynamic Programming with a time complexity of O(n) and space complexity of O(1).