SDE - 1

Approach 1 (Brute Force) :

1) Generate all substrings of string1. 
2) For each substring, check whether the substring contains all characters of string2.
3) Finally, print the smallest substring containing all characters of string2.

TC : O(N^3), where N=length of the given string s1 and s2
SC : O(1)


Approach 2 (Sliding Window) :

We can use a simple sliding window approach to solve this problem.
The solution is pretty intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now.
The answer is the smallest desirable window.

Algorithm :

1) We start with two pointers, left and right initially pointing to the first element of the string S.
2) We use the right pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of T
3) Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one we keep on updating the minimum window size.
4) If the window is not desirable any more, we repeat step2 onwards.

TC : O(N+M) where N and M are the respective length of strings S and T.
SC : O(N+M)

Approach 1 :

1) Sort the array
2) Initially map all the elements of the array to their index in a Hash Map or a Hash Set
3) Now , run 2 for loops and for every x^2 + y^2 ,check if there exists a z^2 s.t x^2+y^2=z^2 and the index of z^2 is different than both the indices of x and y.

TC : O(N^2), where N=size of the array
SC : O(N)


Approach 2 :

1 )We can use a hash map to mark all the values of the given array. 
2) Using two loops, we can iterate for all the possible combinations of a and b, and then check if there exists the third value c. 
3) If there exists any such value, then there is a Pythagorean triplet. 

TC : O(max*max), where max is the maximum most element in the array
SC : O(N), where N = size of the array

Answer :
The answer is O(n). In each step we need traverse both left and right sub-trees in order to search for the minimum element. In effect, this means that we need to traverse all elements to find the minimum.

Approach 1 (Brute Force) :
Solve for each subarray individually.

Algorithm : 

For a particular subarray of size ‘M’:-

1) Sort this subarray as we need to order the integers to find the subarray.
2) Median is calculated as follows:-
2.1) If ‘M’ is odd, the median is the m/2th element of the sorted subarray (0-based indexing is assumed).
3) Else the median is the mean of ‘(M/2-1)th’ and ‘M/2th’ element of the sorted subarray (0-based indexing is assumed).
4) Push the median into the ‘ANS’ vector/list.

TC : O(N * M * log(M)), where ‘N’ denotes the size of array/list and ‘M’ denotes size of the subarray.
SC : O(M), where ‘M’ denotes the size of the subarray.



Approach 2 (Using Multiset) :
We use multiset(self-balance binary tree) because it keeps elements in sorted order and can have multiple occurrences of a number. Declare a multiset 'WINDOWS'.

Algorithm :

1) Insert first 'M' elements in multiset 'WINDOWS'.
2) Calculate median as the mean of value at this iterator and 'M/2-1 + M%2'th position. In case 'M' is odd both iterators point to the same element. 
3) In case 'M' is even first iterator points to 'M/2'th element and the second iterator points to ‘M/2-1’th element.
4) We iterate from 'M' to 'N'-1 for the rest of the subarrays.
5) In each iteration:-
5.1) We remove ‘ARR[i-m]’ from multiset:-
If it is less than mid we decrease iterator 'MID' by ‘1’.
5.2) We insert ‘ARR[i]’ in multiset:-
If it is less than equal to mid we increase iterator 'MID' by ‘1’.
5.3) Calculate 'MEDIAN' in a similar way as described for the first subarray.
6) Finally, we return the array/list ‘ANS’.

TC : O(N * log(M)), where ‘N’ denotes the size of the array/list.
SC : O(M), where ‘M’ denotes the size of the subarray.

Approach 1 (Recursive Inorder Traversal) :

We know that the inorder traversal of a BST always gives us a sorted array , so if we maintain two variable Tree Nodes "previous" and "current" , we should always have previous->val < current->value for a valid BST.

Steps :
1) Create a boolean recursive function with two parameters (root and prev) which will return true if our binary tree is a BST or else it will return false.
2) If root is not null , call the recursive function with parameters (root->left,prev) and check if it return true or not.
3) For the prev node , check if at any point prev->val >= root->val if this condition is met , simply return false.
4) Update prev with root.
5) Call the recursive function again with parameters (root->right , prev)

TC : O(N) where N=number of nodes in the binary tree
SC : O(N)

//Pseudo Code :
bool isValidBST2(TreeNode* root , TreeNode*&prev)
{
//Using inorder traversal
if(root)
{
if(!isValidBST2(root->left,prev))
return false;
if(prev and prev->val >= root->val)
return false;
prev=root;
return isValidBST2(root->right,prev);
}
return true;
}

bool isValidBST(TreeNode*root)
{
TreeNode*prev=NULL;
return isValidBST2(root,prev);
}

Approach 2 (Iterative Inorder Traversal) :

We can also perfom an iterative inorder traversal of the Binary Tree using a stack and check the same condition that we checked above i.e., at any point if prev->value >= current->value if this is met then simply return false.

Steps :
1) Take a stack of TreeNodes and a TreeNode prev with its initial value as NULL.
2) Run a loop till stack is not empty or root != NULL.
3) While pushing a root to the stack, push all its left descendants into the stack untill root != NULL.
4) Take current = stack.top() and pop it from the stack
5) Check if prev is NOT NULL and if prev->val >= curr->val , if this cond. is met simply return false.
6) Update prev with current.
7) Update root with root->right.

TC : O(N) where N=number of nodes in the binary tree
SC : O(N)

//Pseudo Code : 
bool isValidBST(TreeNode* root)
{
stackst;
TreeNode*prev=NULL;
while(!st.empty() || root!=NULL)
{
while(root!=NULL)
{
st.push(root);
root=root->left;
}
root=st.top();
st.pop();
if(prev and prev->val>=root->val)
return false;
prev=root;
root=root->right;
}
return true;
}

Answer : 1 pick of an eatable is required to correctly label the Jars.

Approach : 
1) Pick only one eatable from jar C. Suppose the eatable is a candy, then the jar C contains candies only(because all the jars were mislabeled).

2) Now, since the jar C has candies only, Jar B can contain sweets or mixture. But, jar B can contain only the mixture because its label reads “sweets” which is wrong.

3) Therefore, Jar A contains sweets. Thus the correct labels are:
A : Sweets.
B : Candies and Sweets.
C : Candies.

Approach :

Phone Directory can be efficiently implemented using Trie Data Structure. 

1) We insert all the contacts into Trie.

2) Generally search query on a Trie is to determine whether the string is present or not in the trie, but in this case we are asked to find all the strings with each prefix of ‘str’. This is equivalent to doing a DFS traversal on a graph. 

3) From a Trie node, visit adjacent Trie nodes and do this recursively until there are no more adjacent. This recursive function will take 2 arguments one as Trie Node which points to the current Trie Node being visited and other as the string which stores the string found so far with prefix as ‘str’.

4) Each Trie Node stores a boolean variable ‘isLast’ which is true if the node represents end of a contact(word).

5) User will enter the string character by character and we need to display suggestions with the prefix formed after every entered character.

6) Find the prefix starting with the string formed is to check if the prefix exists in the Trie, if yes then call the displayContacts() function. In this approach after every entered character we check if the string exists in the Trie.

7) Instead of checking again and again, we can maintain a pointer prevNode‘ that points to the TrieNode which corresponds to the last entered character by the user, now we need to check the child node for the ‘prevNode’ when user enters another character to check if it exists in the Trie.

8) If the new prefix is not in the Trie, then all the string which are formed by entering characters after ‘prefix’ can’t be found in Trie too. 

9) So we break the loop that is being used to generate prefixes one by one and print “No Result Found” for all remaining characters.

• The maximum element of the initial array is stored in variable ‘K’
• ‘Count’ array is created with all elements initially being 0, and then the count is incremented every time the number at the index occurs in the array.
• ‘Count’ array is updated for positions by taking the sum of previous elements and storing it as the position for the sorted array.
• Elements are put into the sorted array using a for loop and the function is finally called for sorting a given array.