Blind 75 Flashcards
Deck to revise Blind 75
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Go left, go right, return the max from both at the current node.
If reached leaf node, i.e. no child nodes, return 1.
TC: O(N): Traversing the node.
SC: O(N): Auxiliary stack space.
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
def isSame(tree1, tree2):
# base case
if not tree1 and not tree2:
return True
elif (tree1 and not tree2) or (tree2 and not tree1) or tree1.val!=tree2.val:
return False
left = isSame(tree1.left, tree2.left)
right = isSame(tree1.right, tree2.right)
return left and right
return isSame(p, q)
TC: O(N)
SC: O(N)
Invert Tree
def invert(tree):
# base case
if not tree:
return
# go left
invert(tree.left)
invert(tree.right)
temp = tree.left
tree.left = tree.right
tree.right = temp
invert(root)
return root
TC: O(N)
SC: O(N)
Maximum Product Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Brute:
Algorithm: Traverse with two for loops and get sum
TC: O(N^2)
Optimized Algorithm: Don’t carry negatvie forward
- Traverse the numbers
1.1. if sum_till_now if less than Zero, set it to zero
NOTE: (All negative numbers) Check it first, because if you add the number first and then check the sum to be less than zero, you will set it to zero and
lose a potential max negative number.
1.2. Add current number to sum_till_now
1.3. Update the max_sum, if this is greater.
TC: O(N)
SC: O(1)
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Input: Array of numbers
Output: Longest increasing subsequence
Brute Force Approach
Get all the subsequences.
Check which ones are increasing, and then update the final result (longest length).
Time Complexity: O(2N⋅N)O(2^N \cdot N) (Correct)
Space Complexity: O(N)+O(2N)O(N) + O(2^N)
Optimization
While generating the subsequences, generate only the increasing ones. Otherwise, don’t.
Dynamic Programming (DP) Approach: Overlapping subproblems.
Time Complexity: O(N2)O(N^2) (Correct)
Space Complexity: O(N2)O(N^2) (Can be optimized to O(N)O(N) in some variations)
Rotting Oranges
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Brute:
Minute elapsed when all fresh become rottern
Algorithm:
Count all fresh oranges
Append all Rotten oranges to queue
While queue:
Pop nodes/rotten oranges at current level
Traverse neighbors for each orange, if fresh, rot them now itself (i.e. update grid[r][c]=2, or adding to visited set, to avoid duplicate rots), decrement fresh oranges count and add to queue.
Increment time at this level.
End of while loop
if freshOranges become zero
return time_take
else
return -1
TC: O(N^2)
SC: O(N^2), When all oranges are rotten, you add all of them to queue.
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}</Node>
Test case format:
For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Algorithm
Make a copy of node, store it in map using old_node : new_node
add it to queue
IMPORTANT: Visited set is extremely important in undirected graph BFS traversal, to avoid infinite traversals.
Add any node to queue only when it is not visited, when it is encountered as neighbors of any node.
while(queue):
pop from queue
get the new node from map
traverse the neighbors:
if no new node exist for neighbors, create one, add it to map. Add it to queue.
Add nei new node to curr_new_node
return copy node of original node
TC: O(V+E)
SC: O(V+E)
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
Brute Algorithm
Recursion
Explore all possibilities
A recursive function
Base case: if amount becomes zero, return 0
if index<0: return infinity
if num[index] <= amount:
take = 1 + recursive_function(index, amount-num[index])
not take = recursive_function(index-1, amount)
return min(take, not take)
TC: 2^N
SC: O(Amount/min(coins)
Optimized: Dynamic programming
2D array for storing index, amount combinations
TC: O(amounr * N)
SC: O(amount * N)
Graph Valid Tree
Tell if a graph is Tree or not
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
A graph to be Tree
- It should be Acyclic.
- It should be a single component graph.
TC: O(V+E)
SC: O(V+E)
There is an undirected graph with n nodes. There is also an edges array, where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.
The nodes are numbered from 0 to n - 1.
Return the total number of connected components in that graph.
Traverse the nodes, if not visited, Do DFS, and count the component.
return the total number of component.
TC: O(V+E)
SC: O(V+E)
Merge three triplets to form a triplet
Greedy
Find eligible triplets, that can lead to target triplet.
In the eligible ones, find the maximum value at any index. Because at the end all maximum indexes will be present in the final answer, and hence this state should be equal to target state.
