DSA

Using Top-Down DP(Memoization) – O(m*n) Time and O(m*n) Space C++ Java Python C# JS

Assume we are starting at (1, 1) and want to reach (m, n), given a grid[][] of size m * n. At any moment, should we be on (x, y, we can either proceed to (x, y + 1) or (x + 1, y). The goal is to determine the count of distinct paths should certain grid obstacles be introduced.The grid marks space and an obstruction as 1 and 0 correspondingly. Table of Content Using Recursion – O(2^(m*n)) Time and O(m+n) Space We have covered the issue of counting the distinct paths in a Grid when the grid lacked any obstruction. But here the circumstances are somewhat different. We can come across some barriers in the grid that we cannot leap beyond, hence the path to the bottom right corner is blocked. This method will investigate two primary examples from every cell in both directions: C++ Java Python C# JavaScript Output 2

Problem Statement: Generate Parentheses Given an integer n, generate all combinations of well-formed parentheses of length 2n. A valid combination of parentheses is one where each opening parenthesis ( is properly closed with a closing parenthesis ). Example: Input: n = 3 Output: [“((()))”, “(()())”, “(())()”, “()(())”, “()()()”] Input: n = 1 Output: [“()”] Approach: The problem can be approached using backtracking, which allows us to explore all possible combinations of parentheses while ensuring that at each step, the number of opening parentheses ( is never less than the number of closing parentheses ). Time Complexity: Code Implementation C Code: #include <stdio.h>#include <stdlib.h>#include <string.h>void generateParenthesisRecursive(int n, int open_count, int close_count, char* current, char** result, int* returnSize) { if (open_count == n && close_count == n) { result[*returnSize] = (char*)malloc(strlen(current) + 1); strcpy(result[*returnSize], current); (*returnSize)++; return; } if (open_count < n) { current[open_count + close_count] = ‘(‘; generateParenthesisRecursive(n, open_count + 1, close_count, current, result, returnSize); } if (close_count < open_count) { current[open_count + close_count] = ‘)’; generateParenthesisRecursive(n, open_count, close_count + 1, current, result, returnSize); }}char** generateParenthesis(int n, int* returnSize) { char** result = (char**)malloc(100 * sizeof(char*)); // Assumption: max result size char* current = (char*)malloc(2 * n + 1); *returnSize = 0; generateParenthesisRecursive(n, 0, 0, current, result, returnSize); free(current); return result;}int main() { int returnSize; char** result = generateParenthesis(3, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i]); free(result[i]); } free(result); return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: vector<string> generateParenthesis(int n) { vector<string> result; backtrack(n, 0, 0, “”, result); return result; }private: void backtrack(int n, int open_count, int close_count, string current, vector<string>& result) { if (open_count == n && close_count == n) { result.push_back(current); return; } if (open_count < n) { backtrack(n, open_count + 1, close_count, current + “(“, result); } if (close_count < open_count) { backtrack(n, open_count, close_count + 1, current + “)”, result); } }};int main() { Solution solution; vector<string> result = solution.generateParenthesis(3); for (const string& combination : result) { cout << combination << endl; } return 0;} Java Code: import java.util.ArrayList;import java.util.List;public class Solution { public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); backtrack(n, 0, 0, “”, result); return result; } private void backtrack(int n, int open_count, int close_count, String current, List<String> result) { if (open_count == n && close_count == n) { result.add(current); return; } if (open_count < n) { backtrack(n, open_count + 1, close_count, current + “(“, result); } if (close_count < open_count) { backtrack(n, open_count, close_count + 1, current + “)”, result); } } public static void main(String[] args) { Solution solution = new Solution(); List<String> result = solution.generateParenthesis(3); for (String combination : result) { System.out.println(combination); } }} Python Code: class Solution: def generateParenthesis(self, n: int): result = [] self._backtrack(n, 0, 0, “”, result) return result def _backtrack(self, n: int, open_count: int, close_count: int, current: str, result: list): if open_count == n and close_count == n: result.append(current) return if open_count < n: self._backtrack(n, open_count + 1, close_count, current + “(“, result) if close_count < open_count: self._backtrack(n, open_count, close_count + 1, current + “)”, result)# Example usagesolution = Solution()print(solution.generateParenthesis(3)) # Output: [‘((()))’, ‘(()())’, ‘(())()’, ‘()(())’, ‘()()()’] C# Code: using System;using System.Collections.Generic;public class Solution { public IList<string> GenerateParenthesis(int n) { List<string> result = new List<string>(); Backtrack(n, 0, 0, “”, result); return result; } private void Backtrack(int n, int open_count, int close_count, string current, List<string> result) { if (open_count == n && close_count == n) { result.Add(current); return; } if (open_count < n) { Backtrack(n, open_count + 1, close_count, current + “(“, result); } if (close_count < open_count) { Backtrack(n, open_count, close_count + 1, current + “)”, result); } } public static void Main() { Solution solution = new Solution(); var result = solution.GenerateParenthesis(3); foreach (var combination in result) { Console.WriteLine(combination); } }} JavaScript Code: javascriptCopy codevar generateParenthesis = function(n) { const result = []; function backtrack(current, open_count, close_count) { if (open_count === n && close_count === n) { result.push(current); return; } if (open_count < n) { backtrack(current + “(“, open_count + 1, close_count); } if (close_count < open_count) { backtrack(current + “)”, open_count, close_count + 1); } } backtrack(“”, 0, 0); return result; }; console.log(generateParenthesis(3)); // Output: [“((()))”, “(()())”, “(())()”, “()(())”, “()()()”] Explanation: Time Complexity: Summary: This problem can be efficiently solved using backtracking, where we explore all possible combinations of parentheses while ensuring that each combination is valid. This method generates all valid parentheses combinations for a given n in an optimal way.

Problem Statement: Valid Parentheses Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, and ‘]’, determine if the input string is valid. An input string is valid if: Note: Example: Input: “()” Output: True Input: “()[]{}” Output: True Input: “(]” Output: False Input: pythonCopy code”([)]” Output: pythonCopy codeFalse Input: “{[]}” Output: True Approach: The problem is best solved using a stack data structure. The stack allows us to keep track of opening parentheses, and we can check whether the most recent opening parenthesis matches the closing parenthesis as we iterate through the string. Time Complexity: Code Implementation C Code: #include <stdio.h>#include <stdbool.h>#include <string.h>bool isValid(char* s) { int len = strlen(s); char stack[len]; int top = -1; for (int i = 0; i < len; i++) { char ch = s[i]; if (ch == ‘(‘ || ch == ‘{‘ || ch == ‘[‘) { stack[++top] = ch; } else { if (top == -1) return false; // Stack is empty, unmatched closing bracket char topElement = stack[top–]; if ((ch == ‘)’ && topElement != ‘(‘) || (ch == ‘}’ && topElement != ‘{‘) || (ch == ‘]’ && topElement != ‘[‘)) { return false; // Mismatched parentheses } } } return top == -1; // If the stack is empty, it’s a valid string}int main() { char s[] = “()[]{}”; printf(“Is valid: %s\n”, isValid(s) ? “True” : “False”); // Output: True return 0;} C++ Code: #include <iostream>#include <stack>#include <string>using namespace std;class Solution {public: bool isValid(string s) { stack<char> stack; for (char ch : s) { if (ch == ‘(‘ || ch == ‘{‘ || ch == ‘[‘) { stack.push(ch); } else { if (stack.empty()) return false; // If stack is empty, no matching opening parenthesis char top = stack.top(); stack.pop(); if ((ch == ‘)’ && top != ‘(‘) || (ch == ‘}’ && top != ‘{‘) || (ch == ‘]’ && top != ‘[‘)) { return false; // Mismatched parentheses } } } return stack.empty(); // If stack is empty, all parentheses matched }};int main() { Solution solution; cout << (solution.isValid(“()[]{}”) ? “True” : “False”) << endl; // Output: True return 0;} Java Code: import java.util.Stack;public class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (char ch : s.toCharArray()) { if (ch == ‘(‘ || ch == ‘{‘ || ch == ‘[‘) { stack.push(ch); } else { if (stack.isEmpty()) return false; // Stack is empty, no matching opening parenthesis char top = stack.pop(); if ((ch == ‘)’ && top != ‘(‘) || (ch == ‘}’ && top != ‘{‘) || (ch == ‘]’ && top != ‘[‘)) { return false; // Mismatched parentheses } } } return stack.isEmpty(); // If stack is empty, all parentheses matched } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.isValid(“()[]{}”)); // Output: true }} Python Code: class Solution: def isValid(self, s: str) -> bool: stack = [] mapping = {‘)’: ‘(‘, ‘}’: ‘{‘, ‘]’: ‘[‘} for char in s: if char in mapping: top_element = stack.pop() if stack else ‘#’ if mapping[char] != top_element: return False else: stack.append(char) return not stack # If stack is empty, all parentheses matched# Example Usagesolution = Solution()print(solution.isValid(“()[]{}”)) # Output: True C# Code: using System;using System.Collections.Generic;public class Solution { public bool IsValid(string s) { Stack<char> stack = new Stack<char>(); foreach (char ch in s) { if (ch == ‘(‘ || ch == ‘{‘ || ch == ‘[‘) { stack.Push(ch); } else { if (stack.Count == 0) return false; // Stack is empty, no matching opening parenthesis char top = stack.Pop(); if ((ch == ‘)’ && top != ‘(‘) || (ch == ‘}’ && top != ‘{‘) || (ch == ‘]’ && top != ‘[‘)) { return false; // Mismatched parentheses } } } return stack.Count == 0; // If stack is empty, all parentheses matched } public static void Main() { Solution solution = new Solution(); Console.WriteLine(solution.IsValid(“()[]{}”)); // Output: True }} JavaScript Code: var isValid = function(s) { const stack = []; const mapping = {‘)’: ‘(‘, ‘}’: ‘{‘, ‘]’: ‘[‘}; for (let char of s) { if (char in mapping) { let top = stack.pop() || ‘#’; if (mapping[char] !== top) return false; } else { stack.push(char); } } return stack.length === 0;};console.log(isValid(“()[]{}”)); // Output: true Explanation: Edge Cases: Time Complexity: Summary: The problem is efficiently solved using a stack, which allows us to track the opening brackets and check if they match the closing brackets in the correct order. This ensures that the string is valid if and only if all opening parentheses are properly closed and nested.

A new interval we add could intersect some adjacent intervals in the array. Given the already sorted interval array, one can find overlapping intervals in a contiguous subarray. We identify overlapping interval’s subarray and combine them with new interval to generate a single merged interval. We first add the lower intervals, then this merged interval, and lastly the remaining intervals in the output to preserve the order ordered. C++ Java Python C# JavaScript Output 1 3 4 7 8 10

Given a set of non-overlapping intervals and a new interval, the challenge is to insert the interval at the proper place such that the intervals stay sorted upon insertion. Merge the overlapping intervals should the insertion produce overlapping intervals. Assume that start time drives the sorting of the non-overlapping interval set. Examples are: Table of Content [Simple Approach] Naive Approach Insertion and merging – O(n*log n) Time and O(1) Space The method is to add the new interval to the existing array of intervals and thereafter manage interval overlapping. We shall so combine the overlapping intervals following insertion using the same method as combine Overlapping Intervals. C++ Java Python C# Output 1 3 4 7 8 10

Problem Statement: Letter Combinations of a Phone Number Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on the telephone buttons) is given below. The output should return all possible combinations of letters that can be formed by the digits in the input string. Example: Input: digits = “23” Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”] Input: digits = “” Output: [] Input: digits = “2” Output: [“a”, “b”, “c”] Approach: The problem can be approached by using backtracking or iterative combination generation. We can build the combinations step by step by taking one letter from each digit’s corresponding character set. Steps: Time Complexity: Code Implementation C Code: #include <stdio.h>#include <string.h>#include <stdlib.h>const char* digitToChar[] = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz”};void backtrack(char* digits, int index, char* current, char** result, int* returnSize) { if (index == strlen(digits)) { result[*returnSize] = (char*)malloc(strlen(current) + 1); strcpy(result[*returnSize], current); (*returnSize)++; return; } int digit = digits[index] – ‘0’; for (int i = 0; i < strlen(digitToChar[digit]); i++) { current[index] = digitToChar[digit][i]; backtrack(digits, index + 1, current, result, returnSize); }}char** letterCombinations(char* digits, int* returnSize) { if (digits == NULL || strlen(digits) == 0) { *returnSize = 0; return NULL; } char** result = (char**)malloc(1000 * sizeof(char*)); // Assumption of max size char* current = (char*)malloc(strlen(digits) + 1); *returnSize = 0; backtrack(digits, 0, current, result, returnSize); free(current); return result;}int main() { char digits[] = “23”; int returnSize; char** result = letterCombinations(digits, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i]); free(result[i]); } free(result); return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: vector<string> letterCombinations(string digits) { vector<string> result; if (digits.empty()) return result; vector<string> digitToChar = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” }; string current; backtrack(digits, 0, current, result, digitToChar); return result; }private: void backtrack(const string& digits, int index, string& current, vector<string>& result, const vector<string>& digitToChar) { if (index == digits.size()) { result.push_back(current); return; } int digit = digits[index] – ‘0’; for (char c : digitToChar[digit]) { current.push_back(c); backtrack(digits, index + 1, current, result, digitToChar); current.pop_back(); } }};int main() { Solution solution; vector<string> result = solution.letterCombinations(“23”); for (const string& combination : result) { cout << combination << endl; } return 0;} Java Code: import java.util.ArrayList;import java.util.List;public class Solution { private static final String[] DIGIT_TO_CHAR = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” }; public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); if (digits.isEmpty()) return result; StringBuilder current = new StringBuilder(); backtrack(digits, 0, current, result); return result; } private void backtrack(String digits, int index, StringBuilder current, List<String> result) { if (index == digits.length()) { result.add(current.toString()); return; } int digit = digits.charAt(index) – ‘0’; for (char c : DIGIT_TO_CHAR[digit].toCharArray()) { current.append(c); backtrack(digits, index + 1, current, result); current.deleteCharAt(current.length() – 1); // Backtrack } } public static void main(String[] args) { Solution solution = new Solution(); List<String> result = solution.letterCombinations(“23”); for (String combination : result) { System.out.println(combination); } }} Python Code: from typing import Listclass Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] digit_to_char = [ “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” ] result = [] self._backtrack(digits, 0, “”, result, digit_to_char) return result def _backtrack(self, digits: str, index: int, current: str, result: List[str], digit_to_char: List[str]): if index == len(digits): result.append(current) return digit = int(digits[index]) for char in digit_to_char[digit]: self._backtrack(digits, index + 1, current + char, result, digit_to_char)# Example usagesolution = Solution()print(solution.letterCombinations(“23”)) C# Code: using System;using System.Collections.Generic;public class Solution { private static readonly string[] DigitToChar = { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” }; public IList<string> LetterCombinations(string digits) { var result = new List<string>(); if (string.IsNullOrEmpty(digits)) return result; Backtrack(digits, 0, “”, result); return result; } private void Backtrack(string digits, int index, string current, IList<string> result) { if (index == digits.Length) { result.Add(current); return; } int digit = digits[index] – ‘0’; foreach (char c in DigitToChar[digit]) { Backtrack(digits, index + 1, current + c, result); } } public static void Main() { Solution solution = new Solution(); var result = solution.LetterCombinations(“23”); foreach (var combination in result) { Console.WriteLine(combination); } }} JavaScript Code: var letterCombinations = function(digits) { if (digits === “”) return []; const digitToChar = [ “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” ]; let result = []; function backtrack(index, current) { if (index === digits.length) { result.push(current); return; } let digit = digits[index] – ‘0’; for (let char of digitToChar[digit]) { backtrack(index + 1, current + char); } } backtrack(0, “”); return result;};// Example usageconsole.log(letterCombinations(“23”)); Explanation: Time Complexity:

Under the former method, we iteratively search throughout all the remaining ranges until the end for every range we are looking for potential overlaps. Examining just those intervals that coincide with the latest merged interval will help us maximize this. The intervals will be arranged according on starting point, hence if we come across an interval whose starting time falls outside the last merged interval, all subsequent intervals will likewise lie outside it. First, one sorts the intervals according to their initial places intuitively. Comparing each interval with the last merged interval lets us quickly spot overlapping intervals. Iterate over every interval now; if the current interval crosses the last merged interval, combine both of them. Otherwise, add the resultant combined interval. C++ Java Python C# Output 1 6 7 8

Problem Statement: Longest Common Prefix Given a list of strings, find the longest common prefix (LCP) string amongst them. If there is no common prefix, return an empty string. Note: Example: Input: pythonCopy code[“flower”, “flow”, “flight”] Output: pythonCopy code”fl” Input: pythonCopy code[“dog”, “racecar”, “car”] Output: pythonCopy code”” Approach: There are several methods to solve this problem, but the most common ones include: For simplicity and efficiency, we will use the Horizontal Scanning approach here. Approach (Horizontal Scanning): Time Complexity: Code Implementation C Code: #include <stdio.h>#include <string.h>char* longestCommonPrefix(char **strs, int strsSize) { if (strsSize == 0) return “”; // Initialize the prefix as the first string char *prefix = strs[0]; // Compare with each string for (int i = 1; i < strsSize; i++) { // Keep reducing the prefix while it doesn’t match the start of strs[i] while (strncmp(prefix, strs[i], strlen(prefix)) != 0) { // Reduce the prefix by one character from the end prefix[strlen(prefix) – 1] = ‘\0’; } } return prefix;}int main() { char* strs[] = {“flower”, “flow”, “flight”}; int strsSize = 3; printf(“Longest Common Prefix: %s\n”, longestCommonPrefix(strs, strsSize)); // Output: “fl” return 0;} C++ Code: #include <iostream>#include <vector>#include <string>using namespace std;string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return “”; string prefix = strs[0]; for (int i = 1; i < strs.size(); i++) { while (strs[i].find(prefix) != 0) { prefix = prefix.substr(0, prefix.size() – 1); } } return prefix;}int main() { vector<string> strs = {“flower”, “flow”, “flight”}; cout << “Longest Common Prefix: ” << longestCommonPrefix(strs) << endl; // Output: “fl” return 0;} Java Code: public class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) return “”; String prefix = strs[0]; for (int i = 1; i < strs.length; i++) { while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() – 1); } } return prefix; } public static void main(String[] args) { Solution solution = new Solution(); String[] strs = {“flower”, “flow”, “flight”}; System.out.println(“Longest Common Prefix: ” + solution.longestCommonPrefix(strs)); // Output: “fl” }} Python Code: def longestCommonPrefix(strs): if not strs: return “” prefix = strs[0] for string in strs[1:]: while not string.startswith(prefix): prefix = prefix[:-1] if not prefix: return “” return prefix# Example Usagestrs = [“flower”, “flow”, “flight”]print(“Longest Common Prefix:”, longestCommonPrefix(strs)) # Output: “fl” C# Code: using System;public class Solution { public string LongestCommonPrefix(string[] strs) { if (strs.Length == 0) return “”; string prefix = strs[0]; foreach (var str in strs) { while (!str.StartsWith(prefix)) { prefix = prefix.Substring(0, prefix.Length – 1); if (prefix == “”) return “”; } } return prefix; } public static void Main() { Solution solution = new Solution(); string[] strs = {“flower”, “flow”, “flight”}; Console.WriteLine(“Longest Common Prefix: ” + solution.LongestCommonPrefix(strs)); // Output: “fl” }} JavaScript Code: var longestCommonPrefix = function(strs) { if (strs.length === 0) return ”; let prefix = strs[0]; for (let i = 1; i < strs.length; i++) { while (!strs[i].startsWith(prefix)) { prefix = prefix.substring(0, prefix.length – 1); if (prefix === ”) return ”; } } return prefix;};console.log(longestCommonPrefix([“flower”, “flow”, “flight”])); // Output: “fl” Explanation: Edge Cases: Summary:

The challenge is to combine all the overlapping intervals into one and produce the output which should include only mutually exclusive intervals given an array of time intervals whereby arr[i] = [starti, endi]. As an illustration,: Table of Content [Naive Approach] Checking All Possible Overlaps – O(n^2) Time and O(1) Space One might start from the first interval and compare it with every other interval for overlaps by first grouping all the intervals and then. Eliminate the other interval from the list and combine the other into the first interval if the first interval crosses any other interval. Proceed similarly for the next intervals following the first. C++ Java Python C# JavaScript Output 1 6 7 8