Leetcode Problem 700-799
O(N) Time, Recursive solution
- if root is null return null.
- if rootβs value == val return the root.
- if required value is less than rootβs value, recurse on left subtree.
- else recurse on right subtree.
O(N) Time, Iterative solution
O(N) Time solution
- We append the new node to leaf node where it can be place without violating the BST property.
- if value of new node is less than root we try for right child
- else we try for left child.
O(log N) Time algorithm
- NOTE: Array must be sorted.if not then sort array first.
- Point two variables l and r to the first and last position of array.
- while(l<=r)
- if middle element is target then return middle index
- if middle element is greater than target then r = middle - 1
- if middle element is less than target then l = middle + 1
- if we cant find element in array, return -1.
Solution
- Simple vector solution, Not for interview.
Linked list + Chaining solution
- Implementation for interviews.
- We can use hashing. To handle collision, we can use chaining method.
- We will create a hash function and if a collision happens, we will add the key to the linked list.
Array implementation
- Simple implementation with array.
With the hashing function
- Famous Union-find interview Question
- Nutanix
DFS Solution
Union-find (DSU)
MUST READ:
DFS - Recursive
-
Main function:
- if current color is not new color, call the dfs algorithm.
- else return original image.
-
DFS function:
- check for invalid row and column numbers.
- check if current color is not old color or is already new color.
- for both the cases return.
- set current color to new color.
- call the function for all the 4 directions.
-
Complexity:
- Time: O(M * N), where
M <= 50 is number of rows, N <= 50 is number of columns in the matrix.
- Space: O(M * N), itβs the depth stack memory, in worst case is O(M * N), can check this discussion on stackoverflow.
BFS - Iterative
-
Main function:BFS
- if current color is already new color, return original image
- We need a 2D direction vector and a queue for BFS (q of pairs).
- push starting point in the queue.
- while queue is not empty run loop.
- get the row and column index form the front of the queue, and pop it.
- set current color to new color
- for all directions push {r,c} in the queue if itβs valid.
-
Complexity:
- Time: O(M * N), where
M <= 50 is number of rows, N <= 50 is number of columns in the matrix.
- Space: O(M * N), itβs the depth stack memory, in worst case is O(M * N), can check this discussion on stackoverflow.
MUST READS:
Brute Force
- TC: O(N^2)
- SC: O(1)
- check for every day in an array, if the next day is grater or not.
Stack Solution
- TC: O(N)
- SC: O(N)
- We iterate array from back.
- We use stack to store the index of the days which have greater temperature than the current day.
- Until the top element of the stack is not greater or the stack is empty, we pop the top element.
- After the operation, if stack is empty, we set ith element of ans array to 0, else we set it to
st.top - i.
- return the ans vector.
- similar problem as House robber
House robber - DP
- If we observe here this problem is very similar to House robber problem.
- Since the range of values is upto 10^4, We can calculate how many points we can get from ith number.
- We traverse through the array and store points we can get from ith number.
- We can maximize the points with the same approach as the House robber problem.
Space optimization DP
- Since we are using only last two values we can optimize the space complexity to from 2*10000 to 10000.
Recursive Solution (TLE)
- Since we can start from either step
0 or step 1, the cost to reach these steps is 0.
- We can arrive at step
i from either step i - 1 or step i - 2. Choose whichever one is cheaper.
- Recurrence Relation:
mincost(i) = cost[i]+min(mincost(i-1), mincost(i-2))
- Base cases:
mincost(0) = cost[0]
mincost(1) = cost[1]
- TC: O(2^N)
Memoization (Top-Down) (3ms-AC)
- Since in recursion we are doing lots of redundant calculations, we can use memoization to speed up the process.
- We can use a hash table(memo vector) to store the results of the subproblems.
- Every time if the computation of βnβ is already present return that value, else store new value in memo vector.
- TC: O(N)
- SC: O(N)
Tabulation (Bottom-Up) (7ms-AC)
- We can get rid of that recursive stack with the help of tabulation.
- TC: O(N)
- SC: O(N)
Reduced space complexity
- If we observe our recurrence relation, we just using last and second last values, so we can reduce by using only two variables instead of a vector.
- TC: O(N)
- SC: O(1)
Backtracking
Brute Force (TLE)
- Find all subsequences of s and check if words[i] is in the subsequence.
- TC: O(2^n)
Optimization (TLE)
- Instead of finding all subsequences and checking in words array, we can do opposite of it. i.e. we can find if words[i] is subsequence or not.
- TC: O(n*m), where n = words.size() and m = s.size()
Hashmap (AC)
- We have multiple duplicate words in words array, we can store them and numbers of times they appeared in hashmap and check for subsequence.
- TC: O(n*m), where n = hashmap.size() and m = s.size()
BFS
- We can start from the starting node 0 and traverse every possible next node from the current node.
- Whenever we reach the last node n-1, we will add the path till now into the final answer.
This process can be implemented using a BFS traversal as -
- Initialize a queue of path of nodes with the node 0 inserted into it initially denoting the starting node in our traversal path from 0 to n-1
- Pop an element path from the queue
- Explore every child node of last node in the path. That is, we try every possible edge in graph from node at the end of current path. Each edge added to end of path gives us another path which will be added to queue for further exploration
- If the last node in path is n-1, we know that this is a valid source to target path in the graph. So, we add it to final list of paths
- We repeat this process until the queue is not empty, that is, until there are paths remaining to be explored.
- Time Complexity : O(2^N), where N is the number of nodes in the graph. Every node except the start and end node of graph can either be part of a path or not be part of a path. For a path consisting of k (
3 <= k <= n) nodes, we have k-2 intermediate nodes and we can choose from n-2 available nodes. Thus the resulting time complexity is Ξ£ n-2Ck-2 for all 3 <= k <= n, which comes out to be O(2N-2) = O(2N)
- Space Complexity : O(2^N)
DFS - Backtracking
- We can also solve this problem using DFS traversal.
- This traversal should also be more efficient in terms of space usage as compared to BFS traversal since we are only required to keep a single path in memory at a given time.
- Note that we donβt need to maintain a data structure such as seen to keep track of visited nodes since this is a DAG and thus no recursive dfs call will end up visiting same node twice.
The process of finding all paths using DFS can be implemented as -
Simulation