SkylineWebZ

Given a list indicating words and two separate words, startWord and targetWorda list of distinct words with comparable lengths. Determine which transformation sequences from startWord to targetWord are the shortest. They can be returned in any feasible order. The following requirements must be considered in this problem statement: Examples: Example 1: Input: startWord = “der”, targetWord = “dfs”, wordList = {“des”,”der”,”dfr”,”dgt”,”dfs”} Output: [ [ “der”, “dfr”, “dfs” ], [ “der”, “des”, “dfs”] ] Explanation: The length of the smallest transformation sequence here is 3. Following are the only two shortest ways to get to the targetWord from the startWord : “der” -> ( replace ‘r’ by ‘s’ ) -> “des” -> ( replace ‘e’ by ‘f’ ) -> “dfs”. “der” -> ( replace ‘e’ by ‘f’ ) -> “dfr” -> ( replace ‘r’ by ‘s’ ) -> “dfs”. Example 2: Input: startWord = “gedk”, targetWord= “geek” wordList = {“geek”, “gefk”} Output: [ [ “gedk”, “geek” ] ] Explanation: The length of the smallest transformation sequence here is 2. Following is the only shortest way to get to the targetWord from the startWord : “gedk” -> ( replace ‘d’ by ‘e’ ) -> “geek”. Intuition: The idea behind applying the BFS traversal strategy to these types of issues is that, if we pay close attention, we continue to replace the characters one by one, giving the impression that we are going level-wise to get to the targetWord. It is evident from the example below that there are two ways to get to the targetWord. Since we require all of the shortest sequences to get to the destination word, unlike the prior case, we continue the traversal for as many instances of the targetWord as possible rather than stopping it at the first occurrence. The only difficulty here is that, even if a word matches the changed word during character replacement, we do not have to remove it from the wordList right away. Rather, we remove it whenever the traversal for a specific level is over, enabling us to investigate every potential route. This enables us to find several sequences using related words that lead to the targetWord. We can infer from the preceding image that there are two shortest feasible sequences that lead to the word “cog.” C++ Java Output:  der des dfs  der dfr dfs

The objective is to identify the smallest substring in S that contains every character of P, including duplicates, given two strings S (length m) and P (length n). Return “-1” if there isn’t a substring of that kind. Return the substring with the least starting index if more than one of the same length is found. Examples:  Input: S = “timetopractice”, P = “toc”Output: topracExplanation: “toprac” is the smallest substring in which “toc” can be found. Input: S = “zoomlazapzo”, P = “oza”Output: apzoExplanation: “apzo” is the smallest substring in which “oza” can be found. Table of Content [Naive Method] O(N^3) by Generating Every Substring O(N) Space and Time: Creating every feasible substring from the provided string S and determining if each substring contains every character in the string P is the fundamental principle behind solving this challenge. A helper function that counts the frequency of each character in P and compares it to the frequency of the selected substring can accomplish this checking. The shortest substring is updated in accordance with the current minimum length if a substring contains every character of the P. Until every substring has been examined, the procedure is repeated. C++ C Java Python JS Output toprac Time Complexity: O(N3)Auxiliary Space: O(N) to create substrings.

The aim is to set all rows and columns to zeroes in a constant space complexity matrix of size M x N if a certain element is zero. Examples: Input: [ [1, 1, 1],[1, 0, 1],[1, 1, 1]]Output: [ [1, 0, 1],[0, 0, 0],[1, 0, 1]]Explanation: one zero is present at cell(2,2), and all the elements in the 2nd row and 2nd column are marked as zeroes. Input: [[ 0, 1, 2, 0],[3, 4, 5, 2],[1, 3, 1, 5]]Output: [[0, 0, 0, 0],[0, 4, 5, 0],[0, 3, 1, 0]]Explanation: There are zeroes present in the 1st row at 1st column and 4th column. Native method: C++ Java Python3 JS Output 0 0 0 0 0 4 5 0 0 3 1 0 Time Complexity: O((N*M)*(N + M)) + O(N*M),

The concept is to note the presence of elements inside the same array. Since 1 is the smallest positive integer, first we look to see whether 1 is there; should it be absent, the response is 1. All numbers that are either negative or greater than the array size are converted to 1 otherwise to maintain all numbers within a range of 1 to n. We next index the numbers using their values. To indicate the presence of a number x, we are adding n to the number existing at index x – 1. At last, we search the array for the first unmarked index to obtain the smallest missing positive value. C++ C Java Python JS Output 3

First, all positive integers should be migrated to the left side of the array. We next traverse over this left segment and negating the value at index (x – 1) marks the occurrences of every number x. Finally, go over the left segment once more and, looking for the first unmarked piece, determine the missing number. 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. C++ C Java Python JS Output 3

The concept is like Cycle Sort and moves every element in the array to its proper place depending on its value. Thus, for any number, say x, arrange 1 ≤ x ≤ n at the (x – 1)th index. At last, go over the array looking for whether the numbers match the predicted indexes or not. The first missing positive number results from the first spot where the number does not match its index. The smallest missing positive integer is n + 1, if all the numbers from 1 to n match their proper indices. C++ C Java Python JS Output 3

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];};