DSA

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).

The concept is to keep a window of unique personalities. The window opens as single character. We keep widening the window on the right side till we come upon unique personalities. We erase characters from the left side of the display when we observe a recurring character. We maintain the maximum length window under observation. The comprehensive instructions are below: Starting two points left and right with 0, define the current window under consideration.Extensive the current window, the right pointer goes from left to right.The character at right pointer is indicated as visited should it not be visited.Should the character at right pointer be visited, it indicates a repeated character. Marking visited characters as false, the left cursor advances to the right until the repeated character is no longer part of the current window.Calculated length of the current window (right – left + 1) determines the response modification. C++ C Java Python JS

Table of Content [Naive Approach] Consider substrings starting from every index – O(n ^ 2) Time and O(1) Space Starting from every index and maximum of all such lengths will be our response; we mostly locate length of longest substring with unique characters. We build a new visited array of size 256 (We can also use a hash set, but a visited array would be better because we know that the character set is 256 in most of the cases) to keep track of included characters in the substring in order to ascertain the length of the longest substring with distinct characters starting from an index. C++ C Java Python JavaScript Output 7

A more effective answer to the 2Sum challenge comes from hashing. We loop traverse the items of the array storing each integer in an unordered set instead of verifying every conceivable pair. We find the complement of every number—that is, target less current number—then see whether this complement exists in the set. Should it so, we have located the pair that adds up to the target. This method greatly lowers the time complexity and enables linear time O(n) solution of the problem. Methodically approach: C++ Java Python Js Output 1 Time Complexity: O(n), for single iteration over the arrayAuxiliary Space: O(n), for hashmap

One intends to apply the two-pointer strategy. But the array has to be sorted if one is utilizing the two- pointer approach. Once the array is sorted, we can apply this method retaining one pointer at the beginning (left) and another at the end (right) of the array. Check the sum of the components at these two pointers next as well: C++ C Java Python Output 1 Time Complexity: O(n*log(n)), for sorting the arrayAuxiliary Space: O(1)

Binary search lets us also tackle this issue. Searching element in sorted array will take O(log(n)) time as we know it. First we arrange the array. After that, for every number arr[i] in the array, we first find its complement—that is, target less current number—then apply binary search to rapidly explore the subarray following index i for this complement. We return false if we never discover a complement (after looking over all the numbers); we return true if we do find the complement. C++ C Java Python JS Output 1 Time Complexity: O(n*log(n)), for sorting the arrayAuxiliary Space: O(1)

The aim is to determine whether there is a pair of items in an array whose sum equals the target value given an array arr[] of n integers. The 2Sum problem is a variant of this one. Table of Content [Naive Approach] Generating all Possible Pairs – O(n^2) time and O(1) space The very basic approach is to generate all the possible pairs and check if any of them add up to the target value. To generate all pairs, we simply run two nested loops. C++ C Java Python Output 1 Time Complexity: O(n²), for using two nested loopsAuxiliary Space: O(1)

Problem Statement – Jump Game II You are given an array of non-negative integers nums where each element in the array represents your maximum jump length from that position. Your goal is to reach the last index starting from the first index using the minimum number of jumps. You can assume that you can always reach the last index. Example: Input: nums = [2, 3, 1, 1, 4] Output: 2 Explanation: Jump from index 0 to 1 (nums[0] = 2), then jump from index 1 to 4 (nums[1] = 3). Approach: We are asked to minimize the number of jumps. The optimal approach for this problem is Dynamic Programming (DP) where we keep track of the minimum jumps required to reach each index in the array. Dynamic Programming Explanation: Time Complexity: Optimized Approach: An optimized greedy approach with O(n) time complexity is also possible, where we dynamically track the farthest index we can reach within the current jump range and increment the number of jumps accordingly. Code in Various Languages: 1. C: #include <stdio.h>#include <limits.h>int jump(int* nums, int numsSize) { if (numsSize <= 1) return 0; int dp[numsSize]; for (int i = 0; i < numsSize; i++) dp[i] = INT_MAX; dp[0] = 0; for (int i = 0; i < numsSize; i++) { for (int j = i + 1; j <= i + nums[i] && j < numsSize; j++) { if (dp[j] > dp[i] + 1) { dp[j] = dp[i] + 1; } } } return dp[numsSize – 1];}int main() { int nums[] = {2, 3, 1, 1, 4}; int size = sizeof(nums) / sizeof(nums[0]); printf(“%d\n”, jump(nums, size)); // Output: 2 return 0;} 2. C++: #include <iostream>#include <vector>#include <climits>using namespace std;int jump(vector<int>& nums) { int n = nums.size(); if (n <= 1) return 0; vector<int> dp(n, INT_MAX); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = min(dp[j], dp[i] + 1); } } return dp[n – 1];}int main() { vector<int> nums = {2, 3, 1, 1, 4}; cout << jump(nums) << endl; // Output: 2 return 0;} 3. Java: public class JumpGameII { public int jump(int[] nums) { int n = nums.length; if (n <= 1) return 0; int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = Integer.MAX_VALUE; } dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = Math.min(dp[j], dp[i] + 1); } } return dp[n – 1]; } public static void main(String[] args) { JumpGameII solution = new JumpGameII(); int[] nums = {2, 3, 1, 1, 4}; System.out.println(solution.jump(nums)); // Output: 2 }} 4. Python: def jump(nums): n = len(nums) if n <= 1: return 0 dp = [float(‘inf’)] * n dp[0] = 0 for i in range(n): for j in range(i + 1, min(i + nums[i] + 1, n)): dp[j] = min(dp[j], dp[i] + 1) return dp[n – 1]# Test the functionnums = [2, 3, 1, 1, 4]print(jump(nums)) # Output: 2 5. C#: using System;public class JumpGameII { public int Jump(int[] nums) { int n = nums.Length; if (n <= 1) return 0; int[] dp = new int[n]; for (int i = 0; i < n; i++) dp[i] = int.MaxValue; dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = Math.Min(dp[j], dp[i] + 1); } } return dp[n – 1]; } public static void Main(string[] args) { JumpGameII solution = new JumpGameII(); int[] nums = {2, 3, 1, 1, 4}; Console.WriteLine(solution.Jump(nums)); // Output: 2 }} 6. JavaScript: var jump = function(nums) { let n = nums.length; if (n <= 1) return 0; let dp = new Array(n).fill(Infinity); dp[0] = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j <= i + nums[i] && j < n; j++) { dp[j] = Math.min(dp[j], dp[i] + 1); } } return dp[n – 1];};// Test the functionconst nums = [2, 3, 1, 1, 4];console.log(jump(nums)); // Output: 2 Optimized Approach (Greedy Algorithm) In this approach, instead of using a DP table, we can dynamically track the farthest we can reach in the current jump range, and count how many jumps we need to reach the end. Optimized Approach – Greedy: This approach runs in O(n) time, as we only pass through the array once.

Wildcard Matching Problem In the Wildcard Matching problem, you are given two strings: a text string s and a pattern string p. The pattern string contains two special characters: The goal is to determine if the pattern p matches the entire string s. Problem Statement: Given a string s and a pattern p, return true if p matches s, and false otherwise. Examples: Example 1: Input: s = “aa”, p = “a*”Output: trueExplanation: The pattern “a*” matches the entire string “aa”. Example 2: Input: s = “cb”, p = “?a”Output: falseExplanation: The pattern “?a” does not match the string “cb”. Example 3: Input: s = “adceb”, p = “*a*b”Output: trueExplanation: The pattern “*a*b” matches the string “adceb”. Example 4: Input: s = “acdcb”, p = “a*c?b”Output: falseExplanation: The pattern “a*c?b” does not match the string “acdcb”. Approach: We can solve this problem using Dynamic Programming (DP). Key Observations: Dynamic Programming Approach: We can create a DP table dp[i][j] where: The value dp[i][j] will be true if the substring s[0…i-1] matches the pattern p[0…j-1]. Base Cases: Recurrence Relation: Time and Space Complexity: Code Implementations: 1. C: #include <stdio.h>#include <string.h>#include <stdbool.h>bool isMatch(char *s, char *p) { int m = strlen(s); int n = strlen(p); bool dp[m+1][n+1]; memset(dp, false, sizeof(dp)); dp[0][0] = true; // Both empty string and pattern match // Initialize the first row for patterns starting with ‘*’ for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0][j] = dp[0][j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘?’) { dp[i][j] = dp[i-1][j-1]; // Exact match or ‘?’ } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; // ‘*’ matches one or more characters } } } return dp[m][n];}int main() { char s[] = “adceb”; char p[] = “*a*b”; printf(“%d\n”, isMatch(s, p)); // Output: 1 (true) return 0;} 2. C++: #include <iostream>#include <vector>using namespace std;bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0][j] = dp[0][j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘?’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] == ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; } } } return dp[m][n];}int main() { string s = “adceb”, p = “*a*b”; cout << isMatch(s, p) << endl; // Output: 1 (true) return 0;} 3. Java: public class Solution { public boolean isMatch(String s, String p) { int m = s.length(), n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int j = 1; j <= n; j++) { if (p.charAt(j-1) == ‘*’) { dp[0][j] = dp[0][j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == ‘?’) { dp[i][j] = dp[i-1][j-1]; } else if (p.charAt(j-1) == ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; } } } return dp[m][n]; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.isMatch(“adceb”, “*a*b”)); // Output: true }} 4. Python: def isMatch(s: str, p: str) -> bool: m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for j in range(1, n + 1): if p[j-1] == ‘*’: dp[0][j] = dp[0][j-1] for i in range(1, m + 1): for j in range(1, n + 1): if p[j-1] == s[i-1] or p[j-1] == ‘?’: dp[i][j] = dp[i-1][j-1] elif p[j-1] == ‘*’: dp[i][j] = dp[i-1][j] or dp[i][j-1] return dp[m][n]# Example usage:print(isMatch(“adceb”, “*a*b”)) # Output: True 5. C#: public class Solution { public bool IsMatch(string s, string p) { int m = s.Length, n = p.Length; bool[,] dp = new bool[m + 1, n + 1]; dp[0, 0] = true; for (int j = 1; j <= n; j++) { if (p[j-1] == ‘*’) { dp[0, j] = dp[0, j-1]; } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j-1] == s[i-1] || p[j-1] == ‘?’) { dp[i, j] = dp[i-1, j-1]; } else if (p[j-1] == ‘*’) { dp[i, j] = dp[i-1, j] || dp[i, j-1]; } } } return dp[m, n]; } public static void Main(string[] args) { Solution solution = new Solution(); Console.WriteLine(solution.IsMatch(“adceb”, “*a*b”)); // Output: True }} 6. JavaScript: var isMatch = function(s, p) { const m = s.length, n = p.length; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false)); dp[0][0] = true; for (let j = 1; j <= n; j++) { if (p[j-1] === ‘*’) { dp[0][j] = dp[0][j-1]; } } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (p[j-1] === s[i-1] || p[j-1] === ‘?’) { dp[i][j] = dp[i-1][j-1]; } else if (p[j-1] === ‘*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; } } } return dp[m][n];};// Example usageconsole.log(isMatch(“adceb”, “*a*b”)); // Output: true Summary: