DSA

The visited array will help to track which integers from the original array were present. We note the matching place in the visited array for every positive number in the input array. We then search the visited array looking for the first unvisited point. The first unvisited index reveals the initial missing positive number.We are simply noting numbers falling between 1 and n here. C++ C Java Python JavaScript Output 3

The objective is to determine the smallest positive number that is absent from an unsorted array arr[] that contains both positive and negative items. Note: The initial array is modifiable. Examples: Input: arr[] = {2, -3, 4, 1, 1, 7}Output: 3Explanation: 3 is the smallest positive number missing from the array. Input: arr[] = {5, 3, 2, 5, 1}Output: 4Explanation: 4 is the smallest positive number missing from the array. Input: arr[] = {-8, 0, -1, -4, -3}Output: 1Explanation: 1 is the smallest positive number missing from the array. Table of Content [Naive approach] By Sorting – O(n*log n) Time and O(n) Space Sorting the array will help one to presume a missing number as 1. Now go over the array iteratively and for every element arr[i], Should arr[i] be a missing number, increase missing number by one.Proceed to hunt for the missing number if arr[i] < missing number.Should arr[i] surpass the missing number, break and provide the missing number back. C++ C Java Python JS Output 3

Problem Statement: Unique Binary Search Trees (BSTs) using DP Given a number n, return the total number of unique binary search trees (BSTs) that can be constructed using values 1 through n. The problem is asking for the number of structurally unique BSTs that can be built from n distinct nodes. Example: Time and Space Complexity: Approach: Algorithm: Code Implementation in Multiple Languages: 1. C: #include <stdio.h>int numTrees(int n) { if (n == 0 || n == 1) return 1; int dp[n + 1]; dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; for (int j = 1; j <= i; j++) { dp[i] += dp[j – 1] * dp[i – j]; } } return dp[n];}int main() { int n = 3; printf(“Number of unique BSTs with %d nodes: %d\n”, n, numTrees(n)); return 0;} 2. C++: #include <iostream>#include <vector>using namespace std;int numTrees(int n) { if (n == 0 || n == 1) return 1; vector<int> dp(n + 1, 0); dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j – 1] * dp[i – j]; } } return dp[n];}int main() { int n = 3; cout << “Number of unique BSTs with ” << n << ” nodes: ” << numTrees(n) << endl; return 0;} 3. Java: public class Solution { public int numTrees(int n) { if (n == 0 || n == 1) return 1; int[] dp = new int[n + 1]; dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j – 1] * dp[i – j]; } } return dp[n]; } public static void main(String[] args) { Solution solution = new Solution(); int n = 3; System.out.println(“Number of unique BSTs with ” + n + ” nodes: ” + solution.numTrees(n)); }} 4. Python: def numTrees(n: int) -> int: if n == 0 or n == 1: return 1 dp = [0] * (n + 1) dp[0] = dp[1] = 1 for i in range(2, n + 1): for j in range(1, i + 1): dp[i] += dp[j – 1] * dp[i – j] return dp[n]# Example usage:n = 3print(f”Number of unique BSTs with {n} nodes: {numTrees(n)}”) 5. C#: using System;public class Solution { public int NumTrees(int n) { if (n == 0 || n == 1) return 1; int[] dp = new int[n + 1]; dp[0] = dp[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j – 1] * dp[i – j]; } } return dp[n]; } public static void Main(string[] args) { Solution solution = new Solution(); int n = 3; Console.WriteLine($”Number of unique BSTs with {n} nodes: {solution.NumTrees(n)}”); }} 6. JavaScript: function numTrees(n) { if (n === 0 || n === 1) return 1; const dp = Array(n + 1).fill(0); dp[0] = dp[1] = 1; for (let i = 2; i <= n; i++) { for (let j = 1; j <= i; j++) { dp[i] += dp[j – 1] * dp[i – j]; } } return dp[n];}// Example usage:let n = 3;console.log(`Number of unique BSTs with ${n} nodes: ${numTrees(n)}`); Explanation of the Code: Example Output: For n = 3, the output will be: Number of unique BSTs with 3 nodes: 5 Each of the implementations will compute the same result using dynamic programming.

Problem Statement: Unique Binary Search Trees II: Given an integer n, return all structurally unique BST’s (binary search trees) that store values 1 through n. You need to construct all possible unique BSTs that can be formed with numbers from 1 to n using dynamic programming (DP). Example: Complexity: Approach: Algorithm: Code Implementation: 1. C: #include <stdio.h>#include <stdlib.h>typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;} TreeNode;TreeNode* newNode(int val) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); node->val = val; node->left = node->right = NULL; return node;}TreeNode** generateTrees(int n, int* returnSize) { if (n == 0) { *returnSize = 0; return NULL; } TreeNode*** dp = (TreeNode***)malloc((n+1) * sizeof(TreeNode**)); for (int i = 0; i <= n; i++) { dp[i] = (TreeNode**)malloc((n+1) * sizeof(TreeNode*)); for (int j = 0; j <= n; j++) { dp[i][j] = NULL; } } dp[0][0] = (TreeNode**)malloc(sizeof(TreeNode*)); dp[0][0][0] = NULL; for (int len = 1; len <= n; len++) { for (int i = 0; i <= n – len; i++) { int j = i + len – 1; dp[i][j] = (TreeNode**)malloc(100 * sizeof(TreeNode*)); // Temporary allocation for trees int idx = 0; for (int root = i; root <= j; root++) { TreeNode** left = dp[i][root-1]; TreeNode** right = dp[root+1][j]; if (left == NULL) left = (TreeNode**)malloc(1 * sizeof(TreeNode*)); if (right == NULL) right = (TreeNode**)malloc(1 * sizeof(TreeNode*)); for (int l = 0; left[l] != NULL; l++) { for (int r = 0; right[r] != NULL; r++) { TreeNode* node = newNode(root+1); node->left = left[l]; node->right = right[r]; dp[i][j][idx++] = node; } } } dp[i][j] = realloc(dp[i][j], idx * sizeof(TreeNode*)); } } *returnSize = 0; TreeNode** result = dp[0][n-1]; free(dp); return result;} 2. C++: #include <iostream>#include <vector>using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};vector<TreeNode*> generateTrees(int n) { vector<vector<vector<TreeNode*>>> dp(n + 1, vector<vector<TreeNode*>>(n + 1)); for (int len = 1; len <= n; len++) { for (int i = 0; i <= n – len; i++) { int j = i + len – 1; dp[i][j] = vector<TreeNode*>(100, nullptr); int idx = 0; for (int root = i; root <= j; root++) { vector<TreeNode*> left = dp[i][root – 1]; vector<TreeNode*> right = dp[root + 1][j]; for (auto l : left) { for (auto r : right) { TreeNode* node = new TreeNode(root + 1); node->left = l; node->right = r; dp[i][j][idx++] = node; } } } } } return dp[0][n – 1];} 3. Java: import java.util.ArrayList;import java.util.List;public class Solution { public class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } public List<TreeNode> generateTrees(int n) { List<TreeNode>[][] dp = new List[n + 1][n + 1]; for (int len = 1; len <= n; len++) { for (int i = 0; i <= n – len; i++) { int j = i + len – 1; dp[i][j] = new ArrayList<>(); for (int root = i; root <= j; root++) { List<TreeNode> left = dp[i][root – 1]; List<TreeNode> right = dp[root + 1][j]; for (TreeNode l : left) { for (TreeNode r : right) { TreeNode node = new TreeNode(root + 1); node.left = l; node.right = r; dp[i][j].add(node); } } } } } return dp[0][n – 1]; }} 4. Python: class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef generateTrees(n: int): dp = [[[] for _ in range(n+1)] for _ in range(n+1)] for length in range(1, n+1): for i in range(n-length+1): j = i + length – 1 dp[i][j] = [] for root in range(i, j+1): left = dp[i][root-1] if root > i else [None] right = dp[root+1][j] if root < j else [None] for l in left: for r in right: node = TreeNode(root+1) node.left = l node.right = r dp[i][j].append(node) return dp[0][n-1] 5. C#: public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; }}public class Solution { public IList<TreeNode> GenerateTrees(int n) { List<TreeNode>[][] dp = new List<TreeNode>[n + 1, n + 1]; for (int len = 1; len <= n; len++) { for (int i = 0; i <= n – len; i++) { int j = i + len – 1; dp[i, j] = new List<TreeNode>(); for (int root = i; root <= j; root++) { var left = dp[i, root – 1]; var right = dp[root + 1, j]; foreach (var l in left) { foreach (var r in right) { var node = new TreeNode(root + 1); node.left = l; node.right = r; dp[i, j].Add(node); } } } } } return dp[0, n – 1]; }} 6. JavaScript: function TreeNode(val) { this.val = val; this.left = null; this.right = null;}var generateTrees = function(n) { // DP table to store results for subproblems let dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill([])); // Fill DP table for lengths 1 to n for (let len = 1; len <= n; len++) { for (let i = 0; i <= n – len; i++) { let j = i + len – 1; dp[i][j] = []; // Try each value between i and j as the root for (let root = i; root <= j; root++) { let left = dp[i][root – 1] || [null]; // If there’s no left subtree, use [null] let right = dp[root + 1][j] || [null]; // If there’s no right subtree, use [null] // Combine left and right subtrees with the current root for (let l of left) { for (let r of right) { let node = new TreeNode(root + 1); node.left = l; node.right = r; dp[i][j].push(node); } } } } } // Return the result for trees with nodes from 1 to n return dp[0][n – 1];};

Problem Statement: Decode Ways You are given a string s consisting of digits, where each digit represents a letter according to the following mapping: 1 -> ‘A’2 -> ‘B’…26 -> ‘Z’ Given a string s containing only digits, you need to determine how many ways you can decode it. The decoding rule can be applied multiple times. Approach: We can solve this problem using Dynamic Programming (DP). Let dp[i] represent the number of ways to decode the substring s[0…i-1]. Here’s the approach: Time Complexity: Example: For s = “226”, the possible decodings are: Thus, the result is 3. Code Implementation: 1. C: #include <stdio.h>#include <string.h>int numDecodings(char *s) { int n = strlen(s); if (n == 0 || s[0] == ‘0’) return 0; int dp[n+1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s[i-1] >= ‘1’ && s[i-1] <= ‘9’) dp[i] += dp[i-1]; if (s[i-2] == ‘1’ || (s[i-2] == ‘2’ && s[i-1] <= ‘6’)) dp[i] += dp[i-2]; } return dp[n];}int main() { char s[] = “226”; printf(“Number of decodings: %d\n”, numDecodings(s)); return 0;} 2. C++: #include <iostream>#include <string>using namespace std;int numDecodings(string s) { int n = s.size(); if (n == 0 || s[0] == ‘0’) return 0; int dp[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s[i – 1] >= ‘1’ && s[i – 1] <= ‘9’) dp[i] += dp[i – 1]; if (s[i – 2] == ‘1’ || (s[i – 2] == ‘2’ && s[i – 1] <= ‘6’)) dp[i] += dp[i – 2]; } return dp[n];}int main() { string s = “226”; cout << “Number of decodings: ” << numDecodings(s) << endl; return 0;} 3. Java: public class DecodeWays { public static int numDecodings(String s) { int n = s.length(); if (n == 0 || s.charAt(0) == ‘0’) return 0; int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s.charAt(i – 1) >= ‘1’ && s.charAt(i – 1) <= ‘9’) dp[i] += dp[i – 1]; if (s.charAt(i – 2) == ‘1’ || (s.charAt(i – 2) == ‘2’ && s.charAt(i – 1) <= ‘6’)) dp[i] += dp[i – 2]; } return dp[n]; } public static void main(String[] args) { String s = “226”; System.out.println(“Number of decodings: ” + numDecodings(s)); }} 4. Python: def numDecodings(s: str) -> int: n = len(s) if n == 0 or s[0] == ‘0’: return 0 dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): dp[i] = 0 if ‘1’ <= s[i – 1] <= ‘9’: dp[i] += dp[i – 1] if s[i – 2] == ‘1’ or (s[i – 2] == ‘2’ and ‘0’ <= s[i – 1] <= ‘6’): dp[i] += dp[i – 2] return dp[n]# Example usage:print(numDecodings(“226”)) 5. C#: using System;class DecodeWays { public static int NumDecodings(string s) { int n = s.Length; if (n == 0 || s[0] == ‘0’) return 0; int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = 0; if (s[i – 1] >= ‘1’ && s[i – 1] <= ‘9’) dp[i] += dp[i – 1]; if (s[i – 2] == ‘1’ || (s[i – 2] == ‘2’ && s[i – 1] <= ‘6’)) dp[i] += dp[i – 2]; } return dp[n]; } static void Main() { string s = “226”; Console.WriteLine(“Number of decodings: ” + NumDecodings(s)); }} 6. JavaScript: function numDecodings(s) { let n = s.length; if (n === 0 || s[0] === ‘0’) return 0; let dp = Array(n + 1).fill(0); dp[0] = 1; dp[1] = 1; for (let i = 2; i <= n; i++) { dp[i] = 0; if (s[i – 1] >= ‘1’ && s[i – 1] <= ‘9’) dp[i] += dp[i – 1]; if (s[i – 2] === ‘1’ || (s[i – 2] === ‘2’ && s[i – 1] <= ‘6’)) dp[i] += dp[i – 2]; } return dp[n];}console.log(numDecodings(“226”)); Summary: The solution is efficient and works for strings of moderate length, typically up to 10^3 or 10^4 digits.

The “Scramble String” problem is a classical recursive problem that deals with determining if one string is a scrambled version of another. Problem Statement Given two strings, s1 and s2, check if s2 is a scrambled version of s1. A scrambled string of s1 can be obtained by recursively applying the following operations: Examples Example 1: Input:s1 = “great”, s2 = “rgeat”Output:trueExplanation: Example 2: Input:s1 = “abcde”, s2 = “caebd”Output:false Example 3: Input:s1 = “a”, s2 = “a”Output:true Approach and Algorithm 1. Recursive Approach We recursively check all possible ways to split the strings and validate if either: 2. Dynamic Programming (DP) We use a 3D DP table to store results for substrings of s1 and s2. Complexity Code Implementation C: #include <stdio.h>#include <stdbool.h>#include <string.h>bool isScrambleUtil(char *s1, char *s2, int n) { if (strncmp(s1, s2, n) == 0) return true; if (n == 1) return s1[0] == s2[0]; int freq[26] = {0}; for (int i = 0; i < n; i++) { freq[s1[i] – ‘a’]++; freq[s2[i] – ‘a’]–; } for (int i = 0; i < 26; i++) { if (freq[i] != 0) return false; } for (int i = 1; i < n; i++) { if (isScrambleUtil(s1, s2, i) && isScrambleUtil(s1 + i, s2 + i, n – i)) return true; if (isScrambleUtil(s1, s2 + n – i, i) && isScrambleUtil(s1 + i, s2, n – i)) return true; } return false;}bool isScramble(char *s1, char *s2) { int n = strlen(s1); if (n != strlen(s2)) return false; return isScrambleUtil(s1, s2, n);}int main() { char s1[] = “great”; char s2[] = “rgeat”; printf(“Is Scramble: %s\n”, isScramble(s1, s2) ? “true” : “false”); return 0;} C++: #include <iostream>#include <string>#include <unordered_map>using namespace std;unordered_map<string, bool> memo;bool isScrambleUtil(string s1, string s2) { if (s1 == s2) return true; if (s1.size() != s2.size()) return false; string key = s1 + “#” + s2; if (memo.find(key) != memo.end()) return memo[key]; int n = s1.size(); int freq[26] = {0}; for (int i = 0; i < n; i++) { freq[s1[i] – ‘a’]++; freq[s2[i] – ‘a’]–; } for (int i = 0; i < 26; i++) { if (freq[i] != 0) return memo[key] = false; } for (int i = 1; i < n; i++) { if (isScrambleUtil(s1.substr(0, i), s2.substr(0, i)) && isScrambleUtil(s1.substr(i), s2.substr(i))) { return memo[key] = true; } if (isScrambleUtil(s1.substr(0, i), s2.substr(n – i)) && isScrambleUtil(s1.substr(i), s2.substr(0, n – i))) { return memo[key] = true; } } return memo[key] = false;}bool isScramble(string s1, string s2) { memo.clear(); return isScrambleUtil(s1, s2);}int main() { string s1 = “great”, s2 = “rgeat”; cout << “Is Scramble: ” << (isScramble(s1, s2) ? “true” : “false”) << endl; return 0;} Java: import java.util.HashMap;import java.util.Map;public class ScrambleString { static Map<String, Boolean> memo = new HashMap<>(); public static boolean isScramble(String s1, String s2) { if (s1.equals(s2)) return true; if (s1.length() != s2.length()) return false; String key = s1 + “#” + s2; if (memo.containsKey(key)) return memo.get(key); int n = s1.length(); int[] freq = new int[26]; for (int i = 0; i < n; i++) { freq[s1.charAt(i) – ‘a’]++; freq[s2.charAt(i) – ‘a’]–; } for (int f : freq) { if (f != 0) return memo.put(key, false); } for (int i = 1; i < n; i++) { if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) { return memo.put(key, true); } if (isScramble(s1.substring(0, i), s2.substring(n – i)) && isScramble(s1.substring(i), s2.substring(0, n – i))) { return memo.put(key, true); } } return memo.put(key, false); } public static void main(String[] args) { String s1 = “great”, s2 = “rgeat”; System.out.println(“Is Scramble: ” + isScramble(s1, s2)); }} Python: def isScramble(s1, s2): if s1 == s2: return True if sorted(s1) != sorted(s2): return False n = len(s1) for i in range(1, n): if (isScramble(s1[:i], s2[:i]) and isScramble(s1[i:], s2[i:])) or \ (isScramble(s1[:i], s2[-i:]) and isScramble(s1[i:], s2[:-i])): return True return False# Example Usages1 = “great”s2 = “rgeat”print(“Is Scramble:”, isScramble(s1, s2)) JavaScript: function isScramble(s1, s2) { if (s1 === s2) return true; if (s1.split(“”).sort().join(“”) !== s2.split(“”).sort().join(“”)) return false; let n = s1.length; for (let i = 1; i < n; i++) { if ( (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) || (isScramble(s1.substring(0, i), s2.substring(n – i)) && isScramble(s1.substring(i), s2.substring(0, n – i))) ) { return true; } } return false;}// Example Usagelet s1 = “great”;let s2 = “rgeat”;console.log(“Is Scramble:”, isScramble(s1, s2)); C# using System;using System.Collections.Generic;public class ScrambleString{ // Memoization dictionary to store previously computed results static Dictionary<string, bool> memo = new Dictionary<string, bool>(); // Helper function to check if one string is a scramble of the other public static bool IsScramble(string s1, string s2) { // If both strings are equal, no need to check further if (s1 == s2) return true; // If the lengths of the strings are not the same, return false immediately if (s1.Length != s2.Length) return false; // Create a key for memoization from the two strings string key = s1 + “#” + s2; // If the result for this pair of strings is already computed, return it if (memo.ContainsKey(key)) return memo[key]; // Check if both strings contain the same characters in the same frequency int[] freq = new int[26]; for (int i = 0; i < s1.Length; i++) { freq[s1[i] – ‘a’]++; freq[s2[i] – ‘a’]–; } // If the frequencies don’t match, they cannot be scrambles foreach (var f in freq) { if (f != 0) { memo[key] = false; // Store the result in memoization dictionary return false; } } // Now, check for the two conditions of scrambled strings: for (int i = 1; i < s1.Length; i++) { // Case 1: No swapping of substrings if (IsScramble(s1.Substring(0, i), s2.Substring(0, i)) && IsScramble(s1.Substring(i), s2.Substring(i))) { memo[key] = true; // Memoize the result return true; } // Case 2: Swapping of substrings if (IsScramble(s1.Substring(0, i), s2.Substring(s2.Length – i)) && IsScramble(s1.Substring(i), s2.Substring(0, s2.Length – i))) { memo[key] = true; // Memoize the result return true; } } // If no valid scramble was found, memoize and return false memo[key] = false; return false; } // Main function to test the scramble string function public static

Maximal Rectangle Problem The “Maximal Rectangle” problem is a classical algorithmic challenge where you are given a 2D binary matrix filled with 0‘s and 1‘s. The goal is to find the largest rectangle containing only 1‘s and return its area. Problem Statement: Given a binary matrix, find the area of the largest rectangle containing only 1s. Example: Input: matrix = [ [‘1’, ‘0’, ‘1’, ‘0’, ‘0’], [‘1’, ‘0’, ‘1’, ‘1’, ‘1’], [‘1’, ‘1’, ‘1’, ‘1’, ‘1’], [‘1’, ‘0’, ‘0’, ‘1’, ‘0’]] Output: 6 Explanation: The maximal rectangle is the rectangle with the bottom-right corner at matrix[2][2], spanning 3 columns and 2 rows. Therefore, the area is 3 * 2 = 6. Approach: Algorithm: Code Implementation in Different Languages: C: #include <stdio.h>#include <stdlib.h>int maxHistArea(int *hist, int m) { int *stack = (int *)malloc(m * sizeof(int)); int top = -1, maxArea = 0, area = 0, i = 0; while (i < m) { if (top == -1 || hist[stack[top]] <= hist[i]) { stack[++top] = i++; } else { int height = hist[stack[top–]]; int width = (top == -1) ? i : i – stack[top] – 1; area = height * width; maxArea = (maxArea > area) ? maxArea : area; } } while (top >= 0) { int height = hist[stack[top–]]; int width = (top == -1) ? i : i – stack[top] – 1; area = height * width; maxArea = (maxArea > area) ? maxArea : area; } free(stack); return maxArea;}int maximalRectangle(char **matrix, int n, int m) { int *heights = (int *)calloc(m, sizeof(int)); int maxArea = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { heights[j] = (matrix[i][j] == ‘1’) ? heights[j] + 1 : 0; } int area = maxHistArea(heights, m); maxArea = (maxArea > area) ? maxArea : area; } free(heights); return maxArea;}int main() { char *matrix[] = { “10100”, “10111”, “11111”, “10010” }; int n = 4, m = 5; printf(“Maximal Rectangle Area: %d\n”, maximalRectangle(matrix, n, m)); return 0;} C++: #include <iostream>#include <vector>#include <stack>#include <algorithm>using namespace std;int maxHistArea(vector<int>& hist, int m) { stack<int> st; int maxArea = 0, area = 0, i = 0; while (i < m) { if (st.empty() || hist[st.top()] <= hist[i]) { st.push(i++); } else { int height = hist[st.top()]; st.pop(); int width = st.empty() ? i : i – st.top() – 1; area = height * width; maxArea = max(maxArea, area); } } while (!st.empty()) { int height = hist[st.top()]; st.pop(); int width = st.empty() ? i : i – st.top() – 1; area = height * width; maxArea = max(maxArea, area); } return maxArea;}int maximalRectangle(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int n = matrix.size(), m = matrix[0].size(); vector<int> heights(m, 0); int maxArea = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { heights[j] = (matrix[i][j] == ‘1’) ? heights[j] + 1 : 0; } maxArea = max(maxArea, maxHistArea(heights, m)); } return maxArea;}int main() { vector<vector<char>> matrix = { {‘1’, ‘0’, ‘1’, ‘0’, ‘0’}, {‘1’, ‘0’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘1’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘0’, ‘0’, ‘1’, ‘0’} }; cout << “Maximal Rectangle Area: ” << maximalRectangle(matrix) << endl; return 0;} Java: import java.util.Stack;public class MaximalRectangle { public static int maxHistArea(int[] hist, int m) { Stack<Integer> stack = new Stack<>(); int maxArea = 0, area = 0, i = 0; while (i < m) { if (stack.isEmpty() || hist[stack.peek()] <= hist[i]) { stack.push(i++); } else { int height = hist[stack.pop()]; int width = stack.isEmpty() ? i : i – stack.peek() – 1; area = height * width; maxArea = Math.max(maxArea, area); } } while (!stack.isEmpty()) { int height = hist[stack.pop()]; int width = stack.isEmpty() ? i : i – stack.peek() – 1; area = height * width; maxArea = Math.max(maxArea, area); } return maxArea; } public static int maximalRectangle(char[][] matrix) { if (matrix.length == 0) return 0; int n = matrix.length, m = matrix[0].length; int[] heights = new int[m]; int maxArea = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { heights[j] = (matrix[i][j] == ‘1’) ? heights[j] + 1 : 0; } maxArea = Math.max(maxArea, maxHistArea(heights, m)); } return maxArea; } public static void main(String[] args) { char[][] matrix = { {‘1’, ‘0’, ‘1’, ‘0’, ‘0’}, {‘1’, ‘0’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘1’, ‘1’, ‘1’, ‘1’}, {‘1’, ‘0’, ‘0’, ‘1’, ‘0’} }; System.out.println(“Maximal Rectangle Area: ” + maximalRectangle(matrix)); }} Python: def maxHistArea(heights): stack = [] max_area = 0 i = 0 while i < len(heights): if not stack or heights[stack[-1]] <= heights[i]: stack.append(i) i += 1 else: h = heights[stack.pop()] w = i if not stack else i – stack[-1] – 1 max_area = max(max_area, h * w) while stack: h = heights[stack.pop()] w = i if not stack else i – stack[-1] – 1 max_area = max(max_area, h * w) return max_areadef maximalRectangle(matrix): if not matrix: return 0 n, m = len(matrix), len(matrix[0]) heights = [0] * m max_area = 0 for i in range(n): for j in range(m): heights[j] = heights[j] + 1 if matrix[i][j] == ‘1’ else 0 max_area = max(max_area, maxHistArea(heights)) return max_area# Example Usagematrix = [ [‘1’, ‘0’, ‘1’, ‘0’, ‘0’], [‘1’, ‘0’, ‘1’, ‘1’, ‘1’], [‘1’, ‘1’, ‘1’, ‘1’, ‘1’], [‘1’, ‘0’, ‘0’, ‘1’, ‘0’]]print(“Maximal Rectangle Area:”, maximalRectangle(matrix)) C#: using System;using System.Collections.Generic;public class MaximalRectangle { public static int MaxHistArea(int[] hist, int m) { Stack<int> stack = new Stack<int>(); int maxArea = 0, area = 0, i = 0; while (i < m) { if (stack.Count == 0 || hist[stack.Peek()] <= hist[i]) { stack.Push(i++); } else { int height = hist[stack.Pop()]; int width = stack.Count == 0 ? i : i – stack.Peek() – 1; area = height * width; maxArea = Math.Max(maxArea, area); } } while (stack.Count > 0) { int height = hist[stack.Pop()]; int width = stack.Count == 0 ? i : i – stack.Peek() – 1; area = height * width; maxArea

Given an array of words, print all anagrams together. Input : {“cat”, “dog”, “tac”, “god”, “act”} Output : {“cat”, “tac”, “act”, ‘”dog”, “god”} One could start with a simple hash table creation. Determine each word’s hash value such that every anagram has the same hash value. Stow these hash values into the hash table. Print those words finally beside the same hash values. One can use a basic hash system modulo sum of ASCII values of every character. Modulo sum allows two non-anagram words to have the same hash value. This is to be managed by complementary characters. Another approach to print all the anagrams simultaneously is following. Consider two auxiliary arrays, index array, and word array. Add the specified word sequence to the word array. Sort every individual word in the word array. Sort the word array last then trace the matching indices. All the anagrams gather together following sorting. Print the strings from the original array by means of the index array. Using the following Sequence of Words, let us grasp the procedures: “cat”, “dog”, “tac”, “god”, “act” 1) Create two auxiliary arrays index[] and words[]. Copy all given words to words[] and store the original indexes in index[]  index[]: 0 1 2 3 4 words[]: cat dog tac god act 2) Sort individual words in words[]. Index array doesn’t change. index[]: 0 1 2 3 4 words[]: act dgo act dgo act 3) Sort the words array. Compare individual words using strcmp() to sort index: 0 2 4 1 3 words[]: act act act dgo dgo 4) All anagrams come together. But words are changed in the words array. To print the original words, take the index from the index array and use it in the original array. We get  “cat tac act dog god” C C++ Java Python JS

You are given a string S and a list of words L, which is essentially an array or vector of strings with all the same length. Determine the beginning indices of the substrings in string S, which has every word found in list L. If string S is “barfooapplefoobar” and list of words (L) is [“ foo”, “barfu” then we have to search for substrings “foobar,” “barfu,” in string S. The sequence of words in list L does not matter. Note: Words within the list L can be repeated. Examples : Input : S: “barfoothefoobarman” L: [“foo”, “bar”] Output : 0 9 Explanation : // at index 0 : barfoo // at index 9 : foobar Input : S: “catbatatecatatebat” L: [“cat”, “ate”, “bat”] Output : 0 3 9 Explanation : // at index 0 : catbatate // at index 3 : batatecat // at index 9 : catatebat Input : S : “abcdababcd” L : [“ab”, “ab”, “cd”] Output : 0 2 4 Explanation : // at index 0 : abcdab // at index 2 : cdabab // at index 4 : ababcd Input : S : “abcdababcd” L : [“ab”, “ab”] Output : 4 Approach : We can use Hashing Technique to solve the above problem. Let’s walk through the procedures: Declare a map (hash_map) containing every word from List L matching their occurrences within List L. Go through all conceivable substrings in string S that match size_L (total character count generated if all the words in list L concatenated). For every conceivable substring, first create a temporary map (temp_hash_map) from original map (hash_map). Get the words from the substring; if the word appears in temp_hash_map we reduce its corresponding count; if it does not appear in temp_hash_map we merely break. Following our substring, we search temp_hash_map for any key whose count exceeds 0. Should we discover no such key, all the words in list L were discovered in substring; should we discover a key whose count exceeds 0, we did not traverse the entire substring since we came across a word not in temp_hash_map. C++ Java Python3 JS Output 0 9 Time Complexity : O(N – K) * K N : length of string S. K : total length of list L if all the words are concatenated. If L : [“ab”, “cd”] then K = 4. Space Complexity:  O(K), where K : total length of list L

Allow us to grasp the answer using the example below.arr[{2, 3, 4}First we create all sequences including one digit {2}, obtaining “a,” “b,” and “c.”We then create all sequences with two digits {2, 3}, obtaining “ad,” “ae,” “af,” “bd,” “be,” “bf,” “cd,” “ce,” “cf.” We can just take all past sequences with one digit and one by one add all characters that fit three (“d”, “e“, “f”). We thus have 3 x 3 = 9 sequences.We follow the same procedure for the last digit 4 and get 9 x 3 = 27 needed sequences. The next sequence from the last one now begs the issue of how we got it. We mostly have to handle the FIFO order’s past sequence. For this reason, a queue would be absolutely ideal. We first construct result with i+1 digits by removing every item from queue and adding all characters corresponding to (i + 1)-th digit. We then queue result with i digits. The above method is applied here below: C++ C Java Python JavaScript