DSA

This method mostly serves as an optimization over the last one. The optimizations follow from below observations. We pop one item from the stack and mark current item as next smaller of it while computing next smaller element. Here, one significant note is the item below each item in the stack—the former smaller element. We thus do not have to specifically compute previous smaller. The thorough implementation steps are listed here. C++ C Java Python Output 100

The concept rests on the innocent attitude. We find previous smaller and next smaller for the entire array in linear time instead of linearly finding previous smaller and next smaller for every element. C++ C Java python C# JavaScript

In a given histogram, find the greatest rectangular area that can be formed by a number of contiguous bars with heights provided in an array. Assume for the sake of simplicity that the width of each bar is one unit. Table of Content Simple Approach: O(n^2) Time as well as O(1) Space C++ C Java Python C# JavaScript Output 100

The problem statement is as follows: given a goal value k and an integer array arr of size N, sorted in ascending order (may contain identical values). The array is now rotated at an unidentified pivot point. If k is present, return True; if not, return False. Solution: In a sorted array, how does rotation take place?Consider the following sorted array: {1, 2, 3, 4, 5}. This array will become {4, 5, 1, 2, 3} if we rotate it at index 3. Essentially, we shifted the remaining components to the right and the element at the last index to the front. This procedure was carried out twice. Brute Force Approach The linear search method is one simple strategy we can take into account. In order to determine whether the target is present in the array, we will use this technique to traverse it. We shall just return True if it is found; if not, we will return False. Algorithm: C++ Java Python JavaScript Output: Target is present in the array.Complexity Analysis Time Complexity: O(N), N = size of the given array. Space Complexity: O(1)

This is an iterative method for the recursive method that was previously explained. Here, we attempt to move iteratively in a single direction for every cell. C++ Java python JavaScript

Finding every instance of a given word in a 2D grid with m*n characters is the work at hand. At any given time, a word can be matched in all eight directions. If every character in a word matches in that direction (not in zigzag form), the word is considered to be found in that direction.Horizontally left, horizontally right, vertically up, vertically down, and four diagonal directions are the eight directions. Note: The lexicographically smallest list should be the one that returns. The coordinates should only appear once in the list if the word may be discovered in several directions beginning from the same coordinates. For instance: Table of Content Using Recursion – O(m*n*k) Time and O(k) Space To locate the word, travel to each grid cell and look in all eight directions (up, down, left, right, and diagonals). We also attempt to travel in a single direction for every cell. C++ Java Python C# JavaScript Output {0,0} {0,2} {1,0} Time Complexity: O(m*n*k), where m is the number of rows, n is the number of columns and k is the length of word.Auxiliary Space: O(k), recursion stack space.

Problem: Word Ladder II Problem Statement: Given two words, beginWord and endWord, and a dictionary wordList, find all shortest transformation sequences from beginWord to endWord, such that: Example 1: Input: beginWord = “hit”endWord = “cog”wordList = [“hot”, “dot”, “dog”, “lot”, “log”, “cog”] Output: [[“hit”, “hot”, “dot”, “dog”, “cog”], [“hit”, “hot”, “lot”, “log”, “cog”]] Example 2: Input: beginWord = “hit”endWord = “cog”wordList = [“hot”, “dot”, “dog”, “lot”, “log”] Output: [] Explanation: There is no possible transformation sequence from hit to cog because the word cog is not in the word list. Approach: The problem is essentially about finding the shortest paths in an unweighted graph, where each word is a node, and an edge exists between two nodes if one can be obtained by changing exactly one character. We can break the solution down into two major steps: Step 1: Breadth-First Search (BFS) Step 2: Backtracking Time Complexity: Algorithm: Code Implementation: 1. Python Code from collections import deque, defaultdictdef findLadders(beginWord, endWord, wordList): # Step 1: Edge case – If endWord is not in wordList, return an empty list. if endWord not in wordList: return [] # Step 2: Build a dictionary of all possible intermediate words wordList.add(beginWord) neighbors = defaultdict(list) for word in wordList: for i in range(len(word)): pattern = word[:i] + ‘*’ + word[i+1:] neighbors[pattern].append(word) # Step 3: BFS to find the shortest path length level = {beginWord: [[beginWord]]} # Map to keep track of paths queue = deque([beginWord]) found = False while queue and not found: visited = set() # Keep track of words visited in this level for _ in range(len(queue)): word = queue.popleft() for i in range(len(word)): pattern = word[:i] + ‘*’ + word[i+1:] for neighbor in neighbors[pattern]: if neighbor not in level: level[neighbor] = [] if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # Add the new word to all the possible paths if neighbor == endWord: found = True for path in level[word]: level[neighbor].append(path + [neighbor]) # Move to the next level, after exploring all nodes for the current level for word in visited: level[word] = [path for path in level[word] if path[-1] == word] # Step 4: Return the result return level[endWord]# Example test casebeginWord = “hit”endWord = “cog”wordList = {“hot”, “dot”, “dog”, “lot”, “log”, “cog”}result = findLadders(beginWord, endWord, wordList)print(result) Explanation of the Python Code: 2. C++ Code #include <iostream>#include <vector>#include <unordered_set>#include <unordered_map>#include <queue>#include <string>using namespace std;vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string>& wordList) { vector<vector<string>> result; if (wordList.find(endWord) == wordList.end()) return result; unordered_map<string, vector<vector<string>>> level; // to store the paths at each level unordered_set<string> currentLevel, nextLevel; currentLevel.insert(beginWord); wordList.insert(endWord); bool found = false; while (!currentLevel.empty() && !found) { for (auto& word : currentLevel) wordList.erase(word); // Remove words at this level nextLevel.clear(); for (auto& word : currentLevel) { string temp = word; for (int i = 0; i < word.length(); i++) { char original = temp[i]; temp[i] = ‘*’; // Replace character with * for (auto& neighbor : wordList) { if (neighbor == temp) { if (neighbor == endWord) found = true; for (auto& path : level[word]) { level[neighbor].push_back(path); } nextLevel.insert(neighbor); } } temp[i] = original; } } currentLevel.swap(nextLevel); } for (auto& path : level[endWord]) { result.push_back(path); } return result;}int main() { string beginWord = “hit”, endWord = “cog”; unordered_set<string> wordList = {“hot”, “dot”, “dog”, “lot”, “log”, “cog”}; vector<vector<string>> result = findLadders(beginWord, endWord, wordList); for (const auto& path : result) { for (const auto& word : path) { cout << word << ” “; } cout << endl; } return 0;} Explanation of C++ Code: 3. Java Code import java.util.*;public class WordLadderII { public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { List<List<String>> result = new ArrayList<>(); if (!wordList.contains(endWord)) return result; Map<String, List<List<String>>> level = new HashMap<>(); Set<String> currentLevel = new HashSet<>(); Set<String> nextLevel = new HashSet<>(); currentLevel.add(beginWord); wordList.add(endWord); boolean found = false; while (!currentLevel.isEmpty() && !found) { for (String word : currentLevel) wordList.remove(word); // Remove words at this level nextLevel.clear(); for (String word : currentLevel) { char[] temp = word.toCharArray(); for (int i = 0; i < temp.length; i++) { char original = temp[i]; temp[i] = ‘*’; // Replace character with * String pattern = new String(temp); if (wordList.contains(pattern)) { if (pattern.equals(endWord)) found = true; for (List<String> path : level.getOrDefault(word, new ArrayList<>())) { List<String> newPath = new ArrayList<>(path); newPath.add(pattern); level.computeIfAbsent(pattern, k -> new ArrayList<>()).add(newPath); } nextLevel.add(pattern); } temp[i] = original; // Restore original character } } currentLevel = nextLevel; } return level.getOrDefault(endWord, new ArrayList<>()); } public static void main(String[] args) { WordLadderII wl = new WordLadderII(); Set<String> wordList = new HashSet<>(Arrays.asList(“hot”, “dot”, “dog”, “lot”, “log”, “cog”)); List<List<String>> result = wl.findLadders(“hit”, “cog”, wordList); for (List<String> path : result) { System.out.println(path); } }} Explanation of Java Code: C Code #include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>#include <ctype.h>#include <limits.h>#define MAX_WORDS 1000#define WORD_LENGTH 10typedef struct Node { char word[WORD_LENGTH]; struct Node* next;} Node;typedef struct Queue { Node* front; Node* rear;} Queue;Queue* createQueue() { Queue* queue = (Queue*)malloc(sizeof(Queue)); queue->front = queue->rear = NULL; return queue;}void enqueue(Queue* queue, char* word) { Node* temp = (Node*)malloc(sizeof(Node)); strcpy(temp->word, word); temp->next = NULL; if (queue->rear) { queue->rear->next = temp; } else { queue->front = temp; } queue->rear = temp;}char* dequeue(Queue* queue) { if (queue->front == NULL) return NULL; Node* temp = queue->front; queue->front = queue->front->next; if (queue->front == NULL) { queue->rear = NULL; } char* word = temp->word; free(temp); return word;}bool isAdjacent(char* word1, char* word2) { int diff = 0; for (int i = 0; word1[i] != ‘\0’; i++) { if (word1[i] != word2[i]) { diff++; } if (diff > 1) return false; } return diff == 1;}void findLadders(char* beginWord, char* endWord, char* wordList[], int wordCount) { // BFS approach to find shortest paths Queue* queue = createQueue(); enqueue(queue, beginWord); while (queue->front != NULL) { char* current = dequeue(queue); // If current word is endWord, stop and print the path if (strcmp(current, endWord) == 0) { printf(“Found transformation sequence\n”); return; } for (int i = 0; i < wordCount; i++) { if (isAdjacent(current, wordList[i])) { enqueue(queue, wordList[i]); } } } printf(“No transformation found\n”);}int main() { char* wordList[] = {“hot”, “dot”, “dog”, “lot”, “log”, “cog”}; int wordCount

How many Subsets are possible for an Array of size ‘N’ ? Can we see a relationship of any sort between array N’s size and the number of subgroups it forms before diving into the solution? Yes, there is a relationship, as indicated by the following formula: An array of size N = 2^N has how many subsets? Proof: We have two options for each array element: Option 1: Add it to the subset.Option 2: Take it out of the subset.Total subsets = 2^N since each element has two options for contributing to the subset and there are N elements in total. Let’s examine how this observation can be used to build our solution. Printing all subsets using Backtracking To put the above concept into practice, take the actions listed below: C++ Java Python JavaScript Output 1 1 2 1 2 3 1 3 2 2 3 3 Complexity Analysis:

Problem Statement: Interleaving String Given three strings s1, s2, and s3, the task is to determine if s3 is formed by interleaving s1 and s2 while maintaining the relative order of characters from both strings s1 and s2. A string s3 is said to be an interleaving of s1 and s2 if: Example: Example 1: Example 2: Approach: The problem can be solved using Dynamic Programming (DP). The key idea is to use a 2D DP table where dp[i][j] represents whether the first i characters of s1 and the first j characters of s2 can form the first i+j characters of s3. Algorithm: Complexity: Code Implementations: C: #include <stdio.h>#include <string.h>#include <stdbool.h>bool isInterleave(char *s1, char *s2, char *s3) { int m = strlen(s1); int n = strlen(s2); if (strlen(s3) != m + n) return false; bool dp[m+1][n+1]; memset(dp, 0, sizeof(dp)); dp[0][0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1[i-1] == s3[i+j-1]) { dp[i][j] |= dp[i-1][j]; } if (j > 0 && s2[j-1] == s3[i+j-1]) { dp[i][j] |= dp[i][j-1]; } } } return dp[m][n];}int main() { char s1[] = “abc”; char s2[] = “def”; char s3[] = “adbcef”; if (isInterleave(s1, s2, s3)) { printf(“True\n”); } else { printf(“False\n”); } return 0;} C++: #include <iostream>#include <vector>#include <string>using namespace std;bool isInterleave(string s1, string s2, string s3) { int m = s1.size(), n = s2.size(); if (s3.size() != m + n) return false; vector<vector<bool>> dp(m+1, vector<bool>(n+1, false)); dp[0][0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1[i-1] == s3[i+j-1]) { dp[i][j] |= dp[i-1][j]; } if (j > 0 && s2[j-1] == s3[i+j-1]) { dp[i][j] |= dp[i][j-1]; } } } return dp[m][n];}int main() { string s1 = “abc”, s2 = “def”, s3 = “adbcef”; if (isInterleave(s1, s2, s3)) { cout << “True\n”; } else { cout << “False\n”; } return 0;} Java: public class InterleavingString { public static boolean isInterleave(String s1, String s2, String s3) { int m = s1.length(), n = s2.length(); if (s3.length() != m + n) return false; boolean[][] dp = new boolean[m+1][n+1]; dp[0][0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1.charAt(i-1) == s3.charAt(i+j-1)) { dp[i][j] |= dp[i-1][j]; } if (j > 0 && s2.charAt(j-1) == s3.charAt(i+j-1)) { dp[i][j] |= dp[i][j-1]; } } } return dp[m][n]; } public static void main(String[] args) { String s1 = “abc”, s2 = “def”, s3 = “adbcef”; if (isInterleave(s1, s2, s3)) { System.out.println(“True”); } else { System.out.println(“False”); } }} Python: def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if len(s3) != m + n: return False dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for i in range(m + 1): for j in range(n + 1): if i > 0 and s1[i – 1] == s3[i + j – 1]: dp[i][j] |= dp[i – 1][j] if j > 0 and s2[j – 1] == s3[i + j – 1]: dp[i][j] |= dp[i][j – 1] return dp[m][n]# Test cases1 = “abc”s2 = “def”s3 = “adbcef”print(isInterleave(s1, s2, s3)) # Output: True C#: using System;public class InterleavingString { public static bool IsInterleave(string s1, string s2, string s3) { int m = s1.Length, n = s2.Length; if (s3.Length != m + n) return false; bool[,] dp = new bool[m+1, n+1]; dp[0, 0] = true; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i > 0 && s1[i-1] == s3[i+j-1]) { dp[i, j] |= dp[i-1, j]; } if (j > 0 && s2[j-1] == s3[i+j-1]) { dp[i, j] |= dp[i, j-1]; } } } return dp[m, n]; } public static void Main() { string s1 = “abc”, s2 = “def”, s3 = “adbcef”; if (IsInterleave(s1, s2, s3)) { Console.WriteLine(“True”); } else { Console.WriteLine(“False”); } }} JavaScript: function isInterleave(s1, s2, s3) { let m = s1.length, n = s2.length; if (s3.length !== m + n) return false; let dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false)); dp[0][0] = true; for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i > 0 && s1[i – 1] === s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i – 1][j]; } if (j > 0 && s2[j – 1] === s3[i + j – 1]) { dp[i][j] = dp[i][j] || dp[i][j – 1]; } } } return dp[m][n];}// Test caselet s1 = “abc”, s2 = “def”, s3 = “adbcef”;console.log(isInterleave(s1, s2, s3)); // Output: true Summary:

Problem Statement: Restore IP Addresses Given a string s containing only digits, restore it by returning all possible valid IP address combinations. A valid IP address consists of exactly four integers separated by periods (.), where each integer is between 0 and 255 (inclusive), and no integer has leading zeros unless it is “0”. Example 1: Input: s = “25525511135” Output: [“255.255.11.135”, “255.255.111.35”] Example 2: Input: s = “0000” Output: [“0.0.0.0”] Example 3: Input: s = “1111” Output: [“1.1.1.1″] Approach To solve this problem, we can use backtracking or depth-first search (DFS) to explore all possible valid IP address combinations. Each valid IP address consists of four parts, each part being a number between 0 and 255, and each part must not have leading zeros unless it is exactly “0”. Key Constraints: Plan: Time Complexity: Code Implementation C Code #include <stdio.h>#include <string.h>#include <stdlib.h>void backtrack(char *s, int start, int part, char *current, char **result, int *resultCount) { if (part == 4) { if (start == strlen(s)) { result[*resultCount] = strdup(current); (*resultCount)++; } return; } for (int len = 1; len <= 3; len++) { if (start + len > strlen(s)) break; char temp[len + 1]; strncpy(temp, s + start, len); temp[len] = ‘\0’; // Check validity of the segment if ((len == 1) || (temp[0] != ‘0’ && atoi(temp) <= 255)) { char nextCurrent[100]; snprintf(nextCurrent, sizeof(nextCurrent), “%s%s%s”, current, (part == 0 ? “” : “.”), temp); backtrack(s, start + len, part + 1, nextCurrent, result, resultCount); } }}char** restoreIpAddresses(char* s, int* returnSize) { char **result = (char **)malloc(100 * sizeof(char*)); *returnSize = 0; if (strlen(s) < 4 || strlen(s) > 12) return result; backtrack(s, 0, 0, “”, result, returnSize); return result;}int main() { char s[] = “25525511135”; int returnSize = 0; char **result = restoreIpAddresses(s, &returnSize); printf(“Possible IPs:\n”); 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;void backtrack(string& s, int start, int part, string current, vector<string>& result) { if (part == 4) { if (start == s.size()) { result.push_back(current); } return; } for (int len = 1; len <= 3; len++) { if (start + len > s.size()) break; string temp = s.substr(start, len); // Check validity of the segment if ((len == 1) || (temp[0] != ‘0’ && stoi(temp) <= 255)) { backtrack(s, start + len, part + 1, current + (part == 0 ? “” : “.”) + temp, result); } }}vector<string> restoreIpAddresses(string s) { vector<string> result; if (s.size() < 4 || s.size() > 12) return result; backtrack(s, 0, 0, “”, result); return result;}int main() { string s = “25525511135”; vector<string> result = restoreIpAddresses(s); cout << “Possible IPs:” << endl; for (const string& ip : result) { cout << ip << endl; } return 0;} Java Code import java.util.ArrayList;import java.util.List;public class RestoreIPAddresses { private void backtrack(String s, int start, int part, String current, List<String> result) { if (part == 4) { if (start == s.length()) { result.add(current); } return; } for (int len = 1; len <= 3; len++) { if (start + len > s.length()) break; String temp = s.substring(start, start + len); // Check validity of the segment if ((len == 1) || (temp.charAt(0) != ‘0’ && Integer.parseInt(temp) <= 255)) { backtrack(s, start + len, part + 1, current + (part == 0 ? “” : “.”) + temp, result); } } } public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList<>(); if (s.length() < 4 || s.length() > 12) return result; backtrack(s, 0, 0, “”, result); return result; } public static void main(String[] args) { RestoreIPAddresses solution = new RestoreIPAddresses(); String s = “25525511135”; List<String> result = solution.restoreIpAddresses(s); System.out.println(“Possible IPs:”); for (String ip : result) { System.out.println(ip); } }} Python Code def restoreIpAddresses(s): result = [] def backtrack(start, part, current): if part == 4: if start == len(s): result.append(current) return for length in range(1, 4): if start + length > len(s): break temp = s[start:start + length] # Check validity of the segment if (length == 1) or (temp[0] != ‘0’ and int(temp) <= 255): backtrack(start + length, part + 1, current + (‘.’ if part > 0 else ”) + temp) if len(s) < 4 or len(s) > 12: return result backtrack(0, 0, “”) return result# Example usages = “25525511135”result = restoreIpAddresses(s)print(“Possible IPs:”)for ip in result: print(ip) C# Code using System;using System.Collections.Generic;public class RestoreIPAddresses{ private void Backtrack(string s, int start, int part, string current, List<string> result) { if (part == 4) { if (start == s.Length) { result.Add(current); } return; } for (int len = 1; len <= 3; len++) { if (start + len > s.Length) break; string temp = s.Substring(start, len); // Check validity of the segment if (len == 1 || (temp[0] != ‘0’ && int.Parse(temp) <= 255)) { Backtrack(s, start + len, part + 1, current + (part == 0 ? “” : “.”) + temp, result); } } } public List<string> RestoreIpAddresses(string s) { List<string> result = new List<string>(); if (s.Length < 4 || s.Length > 12) return result; Backtrack(s, 0, 0, “”, result); return result; } public static void Main() { string s = “25525511135”; RestoreIPAddresses solution = new RestoreIPAddresses(); var result = solution.RestoreIpAddresses(s); Console.WriteLine(“Possible IPs:”); foreach (var ip in result) { Console.WriteLine(ip); } }} JavaScript Code const restoreIpAddresses = (s) => { const result = []; const backtrack = (start, part, current) => { if (part === 4) { if (start === s.length) { result.push(current); } return; } for (let len = 1; len <= 3; len++) { if (start + len > s.length) break; const temp = s.slice(start, start + len); // Check validity of the segment if (len === 1 || (temp[0] !== ‘0’ && parseInt(temp) <= 255)) { backtrack(start + len, part + 1, current + (part === 0 ? “” : “.”) + temp); } } }; if (s.length < 4 || s.length > 12) return result; backtrack(0, 0, “”); return result;};// Example usageconst s = “25525511135”;const result = restoreIpAddresses(s);console.log(“Possible IPs:”);result.forEach(ip => console.log(ip)); Explanation: Time and