DSA

The aim is to make a duplicate of a node and place it between the original node and the next node, rather than putting it in a different hash table. New nodes will now be present at different locations. The duplicate of node X will now be X->next, and since it is the duplicate of X->random, the random pointer of the duplicate should point to X->random->next. In order to separate the original linked list from the cloned linked list, iterate over the complete linked list to update the random pointer of each cloned node. To put the concept into practice, take the actions listed below: Make a duplicate of node 1 and place it between nodes 1 and 2 in the original linked list. Then, make a duplicate of node 2 and place it between nodes 2 and 3, and so on. After the Nth node, add the copy of N.Update the random pointers to connect the clone node.Update the following pointers to distinguish the cloned linked list from the original list. C++ Java Python JS Output Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Time Complexity: O(3n), because we are traversing the linked list three times. Auxiliary Space: O(1), as we are storing all the cloned nodes in the original linked list itself, no extra space is required.

Determine the length of the largest subsequence in an integer array where the components are consecutive integers; the numbers can be in any order. Examples:   Input: arr[] = {1, 9, 3, 10, 4, 20, 2}Output: 4Explanation: The subsequence 1, 3, 4, 2 is the longest subsequence of consecutive elements Input: arr[] = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42}Output: 5Explanation: The subsequence 36, 35, 33, 34, 32 is the longest subsequence of consecutive elements. [Naive Approach] Using Sorting – O(N*logN) Time and O(N) Space: Finding the longest subarray with consecutive elements is the first step in sorting the array. Run a loop after sorting the array and eliminating entries that appear more than once, maintaining a count and max (both originally zero). Run a loop from beginning to end, setting the count to 1 if the current element is not equal to the previous (element+1); otherwise, increase the count. With a maximum of count and max, update max. To solve the issue, take the actions listed below: C++ Java Python JS Output Length of the Longest contiguous subsequence is 3 Time complexity: O(Nlog(N)), Time to sort the array is O(Nlog(N)).Auxiliary space: O(N). Extra space is needed for storing distinct elements.

Problem Statement: Interleaving String Given three strings, s1, s2, and s3, determine if s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s1 and s2 is formed by inserting characters of s1 and s2 in such a way that the relative order of characters in both strings is preserved. For example: Here, s3 is an interleaving of s1 and s2, so the answer is True. Constraints: Dynamic Programming Approach We can solve this problem using a 2D DP table. Time Complexity: Code Implementation in Different Languages 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 (m + n != strlen(s3)) return false; bool dp[m + 1][n + 1]; memset(dp, false, 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][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];}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 (m + n != s3.size()) 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][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];}int main() { string s1 = “abc”, s2 = “def”, s3 = “adbcef”; if (isInterleave(s1, s2, s3)) { cout << “True” << endl; } else { cout << “False” << endl; } return 0;} Java: public class Main { public static boolean isInterleave(String s1, String s2, String s3) { int m = s1.length(), n = s2.length(); if (m + n != s3.length()) 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][j] || dp[i – 1][j]; } if (j > 0 && s2.charAt(j – 1) == s3.charAt(i + j – 1)) { dp[i][j] = dp[i][j] || dp[i][j – 1]; } } } return dp[m][n]; } public static void main(String[] args) { String s1 = “abc”, s2 = “def”, s3 = “adbcef”; System.out.println(isInterleave(s1, s2, s3) ? “True” : “False”); }} Python: def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if m + n != len(s3): 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][j] or dp[i – 1][j] if j > 0 and s2[j – 1] == s3[i + j – 1]: dp[i][j] = dp[i][j] or dp[i][j – 1] return dp[m][n]# Example Usages1 = “abc”s2 = “def”s3 = “adbcef”print(“True” if isInterleave(s1, s2, s3) else “False”) C#: using System;class Program { public static bool IsInterleave(string s1, string s2, string s3) { int m = s1.Length, n = s2.Length; if (m + n != s3.Length) 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, 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]; } static void Main() { string s1 = “abc”, s2 = “def”, s3 = “adbcef”; Console.WriteLine(IsInterleave(s1, s2, s3) ? “True” : “False”); }} JavaScript: function isInterleave(s1, s2, s3) { const m = s1.length, n = s2.length; if (m + n !== s3.length) return false; const 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];}// Example Usagelet s1 = “abc”, s2 = “def”, s3 = “adbcef”;console.log(isInterleave(s1, s2, s3) ? “True” : “False”); Summary:

Two terms of the same length, “start” and “target,” are provided in a dictionary. Determine the length of the smallest chain, if any, between “start” and “target,” such that each word in the chain is a legitimate word—that is, it appears in the dictionary—and that adjacent words in the chain differ by no more than one character. It is reasonable to assume that the “target” term is present in a dictionary and that all dictionary words have the same length. Example:  Input: Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}, start = TOON, target = PLEAOutput: 7Explanation: TOON – POON – POIN – POIE – PLIE – PLEE – PLEA Input: Dictionary = {ABCD, EBAD, EBCD, XYZA}, start = ABCV, target = EBADOutput: 4Explanation: ABCV – ABCD – EBCD – EBAD Approach: Using BFS is the suggested solution to the issue. Start with the start word and push it in a queue to determine the shortest path via BFS. Return that level of BFS traversal after the target is located for the first time. All of the phrases that can be created with that many stages are available in each BFS step. Thus, the length of the shortest word chain will be the first time the target word is discovered. C++ Java Python JS Output Length of shortest chain is: 7 Time Complexity: O(N * M), where N is the number of entries originally in the dictionary and M is the size of the string.Auxiliary Space: O(N+M)

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