Leetcode Problem 100-199

100. Same Tree 🌟

Intuitive recursive solution

self explanatory

Recursive to iterative using queue

101. Symmetric Tree 🌟

O(N) Time solution

we will traverse left and right subtrees of the root with the same type of traversal.
we compare the value of left with right or value of right with left , if they are not equal we return false.
we recurse for left’s left with right’s right and left’s right with right’s left.

O(N) Time, using 2 queue, iterative solution

Same recursive solution can be converted to iterative solution by using queue.
Remember while using 2 queue we push left->left,left->right in 1st queue and right->right,right->left in 2nd queue.

O(N) Time, using 1 queue, iterative solution

We can use 1 queue instead of 2.
remember that while using 1 queue we do left->left,right->right,left->right,right->left.

102. Binary Tree Level Order Traversal 🌟🌟

O(N) Time and O(N) Space

Create an empty queue q.
Push the root node of tree to q.
Loop while the queue is not empty:
- get all the elements of q.
- push their left and right nodes in the queue.
- push_back these elements in the vector.
- pus_back this vector in main 2d vector.
return 2d vector.

103. Binary Tree Zigzag Level Order Traversal 🌟🌟

This question is in continuation with A general approach to level order traversal questions series.

Prerequisites:

Recursive solution

Here is just one change, if level is odd we insert value at the beginning of vector, otherwise at the end.

Iterative solution

Same code, just reversed the current level vector if result vector has odd size.
Reason for above operation: since in the example we can observe every even vector is reversed, we have to reverse the even level vector, so at that time res vector has odd size.

Without reverse, insert at front if odd (Fastest)

Here, just like we did in Q107, we just insert at the beginning of vector if res vector size is odd(i.e. currLevel is even).

104. Maximum Depth of Binary Tree 🌟

O(N) Time and O(H) Space,(DFS) More proffered than iterative

Worst case, if tree is skewed then it will take O(N) else O(h) space, where h is the height of the tree.
If root is null then return 0.
else return 1 + maximum depth of(left subtree, right subtree)

O(N) Time and O(N) Space (BFS), using level order traversal

Same like level order traversal, but we need to keep track of the depth.

105. Construct Binary Tree from Preorder and Inorder Traversal 🌟🌟

Solution

To solve this problem we need to remember preorder and inorder of tree
Preorder = root, left, right
Inorder = left, root, right
So We can notice that if we start from root we will get root of the tree
by finding position of root in inorder we can say that, entire section which is on left to the root is its left subtree and right of the root is right subtree.
by dividing it we again got a smaller subtree, so we need to also it recursively by dividing till its base condition
We can loop over to inorder array to find elements index, but it will add extra O(N) time complexity per operation.
so instead of that we can use map to store indexes of inorder to reduce the time complexity.
TC: O(N)
SC: O(N)

106. Construct Binary Tree from Inorder and Postorder Traversal 🌟🌟

MUST READ

[[C++] EASY Intuitive Sol

Clean Recursive Code w/ Explanation

T.C:O(N)](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/1588934/C%2B%2B-EASY-Intuitive-Sol-oror-Clean-Recursive-Code-w-Explanation-oror-T.C%3AO(N))

107. Binary Tree Level Order Traversal II 🌟🌟

Recursive solution

The code is same as level-order-traversal, just 2 modifications.
1. We have to insert New vector to the beginning of the result vector.
2. We have to insert values at res.size() - 1 - level position.

Iterative solution

It is also same as level-order-traversal, just we return the reverse of the result vector.

Iterative Solution without reverse

If you don’t want to reverse the vector, you can insert new level directly to the beginning of the result vector.
But as compared to previous solution, this solution is takes more time to execute.

110. Balanced Binary Tree 🌟🌟

Brute force

For every node calculate the height of the left subtree and right subtree.
If the difference between the height of the left subtree and right subtree is greater than 1, return false.
Else return true.
Time complexity: O(N^2), as every time we are calculating the height of the tree.
Space complexity: O(N)

Optimized

We will use same approach as find the height of the tree.
As we know every time we know the height of the left and right subtree, so we can calculate the diameter of the tree at this point.
Just keep track of the maximum diameter of the tree in height of BT code.
Time complexity: O(N)
Space complexity: O(N)

112. Path Sum 🌟

O(N) Time , recursive

if root is null return false
if roots left and right both are null return root->val==targetSum.
else recursively find targetSum - root->val in left and right subtree.

O(N) Time , iterative

soon…

116. Populating Next Right Pointers in Each Node 🌟🌟

This question is in continuation with A general approach to level order traversal questions series.

Previous Questions

Next 2 solutions are part of the series other are not.

Recursive Solution

self explanatory

Iterative Solution

Self explanatory

O(N) Time and O(N) space

Using level order traversal technique and NULL.
if current node is null and q is not empty, then push NULL into q.
else set current node’s next to q’s front.
push left and right in the queue , if they are not NULL.

O(N) Time and O(1) space

level order traversal with root and its child,just dry run once you get the idea.

118. Pascal’s Triangle 🌟

Straightforward solution

We can find any element(a[i][j]) in O(1) time using the formula (r-1)C(c-1) i.e (r-1)!/(c-1)!

Ex. 3rd element of 5th row -> c=2,r=4 -> (4*3)/(2*1) = 6.

119. Pascal’s Triangle II 🌟

120. Triangle 🌟🌟

Recursion(TLE)

If we are at the last row, return the element.
else try going down and right diagonally, take minimum of both.
return current element + min of both.

Memoization (AC)

The recursive code gives TLE.
We can use memoization to solve this problem.
Take 2D array memo to store the result.

Dynamic Programming (AC)

121. Best Time to Buy and Sell Stock 🌟

O(N^2) Time and O(1) Space

Brute force:
For each day, find the max profit that can be made by buying at that day and selling at the next j days.

O(N) Time and O(N) Space

We try to sell stock each day.
For each day from last we store maximum stock price that will appear.
then for each day we calculate by selling the stock.

O(N) Time and O(1) Space

We try to buy stock each day.
For each day we keep track of the minimum price of the stock that appeared before it.
if todays stock price is minimum we will update it.
return max profit.

Optimized inner loop : 33% less time.

If the price of the stock that day less than minimum price so far then there is no chance to get profit so we only update minimum price.
else we can get profit, update maxProfit.

122. Best Time to Buy and Sell Stock II 🌟🌟

Greedy - O(N) Time O(1) space (Valley-peak approach)

O(2^N) and O(N^2) approaches
For each time at lowest cost(valley) we buy stock and at highest cost(peak) we sell stock.
for each day we buy and on next day we sell, If it is profitable

READ:

✅ [Java] Simple & Clean DP solutions for all 6 Buy & Sell Stock questions on LeetCode

123. Best Time to Buy and Sell Stock III 🌟🌟🌟

Recursive Solution (TLE)

For a day we have 2 choices, either can buy stock or sell stock.
We can do 2 total transactions(buy & sell) that means we have total 4 individual transactions(buy,sell,buy,sell).
if we have even transactions remaining then we buy stock else we sell stock.
for every day we return maximum of (doing nothing, buy/sell stock).
At any point we finish all our transactions we return 0 also if we don’t have days left from trading we return 0.
TC: O(2^n)
SC: O(n)

Memoization (AC)

The recursive solution giving TLE because of so many subproblems calculated again and again.
We can remember the result of subproblems in dp array.
If we already calculated the result of subproblems then we can directly return the result, else we store new calculations in table.
TC: O(N)
SC: O(N)

Tabulation (AC)

Tabulation starts from base cases as its the bottom up approach.
from memoization solution we can write tabulation method easily
TC: O(N)
SC: O(N)

Tabulation | space optimization (AC)

We can observe that, for any day we just need the answers of the next day, so we can reduce space complexity to O(1).
TC: O(N)
SC: O(1)

128. Longest Consecutive Sequence 🌟🌟

Sorting Solution

TC: O(NlogN)
sort the sequence and find the consecutive subsequences and out of them return the length of the longest consecutive subsequence.

Hash table O(N) Time solution

we create hash table of nums.
for every element we check if num-1 is present or not.
if its not present then from num we count num,num+1,num+2,... consecutive elements.
when num+.. not found we update our ans.
return ans.

129. Sum Root to Leaf Numbers 🌟🌟

O(N) Time recursive

We recursively traverse to the all leaf node.
Multiply val by 10 and add curr val in it.
if both left and right child is null, we add the current node value to the sum.
else recurse for left anf right subtree.
Stack can grow upto the height of the tree so that we can explore the path from root to leaf node.
Thus, Space Complexity = O(Height of the tree)
Time Complexity:O(N) –> All Nodes will be visited once.

Useful Comment:

List of problems you need to master the concept :

If you find more problems, please comment it below :)

130. Surrounded Regions 🌟🌟

DFS Approach complex

This video explains both the approaches and code.
1st approach is complex while 2nd is easy.

DFS Approach more efficient

Pick all O’s from boundary (Top/Bottom row, Leftmost/Rightmost column)
Make all connected O’s to some intermediate value (1 in my case).
Now remaining all O’s are surrounded by X (otherwise they should have been converted to 1).
Convert remaining all O to X.
Revert all intermediate values. (1 to O).
Time Complexity - O(m * n)
Space Complexity - O(1) if we ignore recursive stack calls else O(m * n)

131. Palindrome Partitioning 🌟🌟

Backtracking solution

133. Clone Graph 🌟🌟

Solution

To clone a graph, you will need to traverse it.
Both BFS and DFS are for this purpose. But that is not all you need.
To clone a graph, you need to have a copy of each node and you need to avoid copying the same node for multiple times.
So you still need a mapping from an original node to its copy.

DFS Solution

We need map to store copies of node.
We pass node and map in dfs function.
DFS:
if node is already visited, return the node
else create a new node and add it to the map
add all the neighbors of the node in the new node(add dfs)
return new node

BFS Solution

create a map to store the cloned nodes & queue for bfs
create a new node with the same value as the original node
and add it to the map
BFS:
add all the neighbors of the node in the new node
if x is not in the map
add x->val in the map
add x to the queue
add x to the neighbors of the cloned node

134. Gas Station 🌟🌟

Greedy Solution

The sum of gas[i] - cost[i] (which is the current balance state) from start point should always be >= 0, otherwise, we can’t move to the next point.
TC: O(N)
SC: O(1)

136. Single Number 🌟

Sorting array

Using Map

Using XOR (^)

XOR of same numbers is 0;
XOR of 0 with a number is the number;

138. Copy List with Random Pointer 🌟🌟

Brute force

Take hashmap<originalNode,copyNode>
Traverse the linked list and create deep copy of the current node and push both in the hashmap.
Now traverse the linked list again and point deep copied node to the other deep copy nodes as present in original node.
TC: O(N)
SC: O(N)

Optimized

3 Step algorithm explained in code.
TC: O(N)
SC: O(1)

141. Linked List Cycle 🌟

O(N) Time and O(N) space

If there is a cycle in given linked list then same node must appear more than once.
so, we create an unordered_set of nodes ands while traversing the list we check if the node is already present in the linked list.
if its present we return true else we insert it into the unordered_set.
finally after completing loop we return false. because there is no cycle.

O(N) Time and O(1) space - floyd’s cycle detection algorithm

Here fast pointer move 2 steps and slow pointer moves one step.
If they meet each other while traversing then loop that means there is a cycle else not.

142. Linked List Cycle II 🌟🌟

fast ans slow pointer Solution

We can use fast and slow pointer method to find the cycle.
We move fast by 2 steps and slow by 1 step.
When they both are equal, we have found the cycle, else we return null.
If cycle found set fast pointer to head again and move both by 1 step.
when both of then are equal, we have found the start of the cycle.
return the fast/slow pointer.
TC: O(N)
SC: O(1)

143. Reorder List 🌟🌟

Most intuitive (Using stack)

To access the last node fist we can use the stack.
Count the length & push node in stack.
for half of the length we can just reorder the list.
- take the top of the stack.
- nxt is the next node of the currNode
- set current node's next to the top of the stack.
- set the next of the stack's top to nxt.
- finally set curr to nxt.
Set the last node's next to NULL.
TC: O(N)
SC: O(N)

Using Dequeue

Push all the nodes into a dequeue and popping alternatively from front and back while reordering the elements.
TC: O(N)
SC: O(N)

144. Binary Tree Preorder Traversal 🌟

O(N) Time O(N) space (function call stack), Recursive

if root is null, Return.
Visit the root (store data).
Traverse Left subtree.
Traverse Right subtree.

O(N) Time and O(N) extra space

Create a vector to store values and stack for operations
if tree is empty, return empty vector
else push root into stack
while stack is not empty
- pop the top element from stack
- push the value of the popped element into vector
- we want left node to the top of stack, so we store it last so it appear on the top of stack
- if right node is not empty, push it into stack
- if left node is not empty, push it into stack

Morris traversal - O(N) time and O(N) space.

Explanation soon…

145. Binary Tree Postorder Traversal 🌟

O(N) Time and O(2N) space, Iterative

NOTE: Here instead of *2 Stack* I have used *1 Stack and 1 vector* and reversed the vector at the end.

More detail explanation watch this 4 min video.

O(N) Time and O(N) Space, Iterative (1 stack)

This is bit tricky.Dry run 2-3 trees to understand Watch this Video.

O(N) Time and O(1) Space, Morris traversal

soon…

148. Sort List 🌟🌟

Intuitive Approach

Store all the values of the nodes in the array.
Sort the array.
Create new Linked List from the sorted array.

merge sort

Same like array merge sort.

150. Evaluate Reverse Polish Notation 🌟🌟

Stack Solution

This is simple stack problem.
We use stack to store the numbers in the expression.
If we encounter an operator, we pop the top two numbers ‘b’ and ‘a’ respectively(order matters for ‘-‘ and ‘/’).
Then we calculate the result and push it back to the stack.
And if its number we simply push it to the stack.
Finally we return the top of the stack, which contains the result.
TC: O(N)
SC: O(N)

152. Maximum Product Subarray 🌟🌟

Brute Force

We want to find maximum product subarray, so we can just create all subarrays and find maximum product subarray among them.
TC: O(N^2)
SC: O(1)

Kaden’s algorithm

TC: O(n)
SC: O(1)

155. Min Stack 🌟

TIP

Solving a question to implement stack using stack is possible , but not a good idea.
you can use 2 vector, 1 vector, vector of pair or map to implement the stack.

Time Complexity: O(1) for all the solutions.

Space Complexity: Extra O(N) Space used.

Using 2 Vectors

We maintain 2 vectors, 1 for stack implementation and another for min stack.push INT_MAX to min stack in declaration.
push operation:
- push element to stack.
- push min element to min stack.
pop operation:
- pop element from stack.
- pop min element from min stack.
top operation:
- return top element from stack.
getMin operation:
- return top element from min stack.

Using 1 vector

Instead of 2 vectors, we can use 1 vector to implement the stack.
push operation:
- if minElement is greater or equal to val, push minElement to stack and update minElement to val.
- then push val in the stack.
pop operation:
- pop the top of the stack.
- if top is equal to minElement, minElement will be top(next top) of the stack and pop the top(next top) from stack.

Using vector of pair

Self explanatory code

165. Compare Version Numbers 🌟🌟

split and compare (two pass)

split both strings on ‘.’ and store numbers in vectors.
compare each element and return the ans.
TC: O(N), N=length of max(version1, version2)
SC: O(N), N=length of max(vector1, vector2)

167. Two Sum II - Input array is sorted 🌟

O(N) Time 2-pointers solution

We maintain 2 pointers, one at the start and one at the end.
We iterate over the array.
- If Sum if equal to target, return the indices.
- else if sum is greater than target we decrement the end pointer.
- else we increment the start pointer.

169. Majority Element 🌟

O(N^2) Brute force

For every number in array we count its occurrences.
If count is greater than n/2, then we return the number.

O(N)Time with extra space

we Can take a vector or unordered_map to store the frequency of each element.
We traverse the hash map/ vector to find the n/2 frequency.
if we found we return the element.
TC: O(N)
SC:O(N)/O(N^2) - Yes if we use unordered_map it’s worst case time complexity is O(N^2), which occurs when all elements are divisible by prime number and result in collision. But if we use frequency vector it’s worst case time complexity is O(N).

Moore’s Voting Algorithm

TC:O(N)
SC:O(1)
We maintain 2 variables count and candidate.
We traverse the array and for every element we do following:
- If count is 0, then we set candidate as current element.
- If current element is same as candidate, then we increment count by 1.
- else we decrement count by 1.
return candidate.

171. Excel Sheet Column Number 🌟

Intuitive Solution (AC)

We can observe that the number formed is like 26 base number system represented in capital letters.
We can for number with char*26+carry formula.
TC: O(N)
SC: O(1)

188. Best Time to Buy and Sell Stock IV 🌟🌟🌟

Recursion (TLE)

for the i’th day if we are holding a stock we can either sell it or do nothing.
if we are not holding a stock we can either buy it or do nothing.
The base case arises when we completed all the transactions(k == 0) OR we are done for all days(i == prices.size()).

Note that you could also set up the solution so that transactions are completed upon buying a stock instead.

Memoization (AC)

In the recursive version, we have to calculate the same subproblem multiple times.
we can reduce the number of subproblems by storing the results of the subproblems.
we use 3D array to store the results.
TC : O(N * K)
SC : O(N * K)

Tabulation (AC)

The recurrence relation is the same with top-down, but we need to be careful about how we configure our for loops.
The base cases are automatically handled because the dp array is initialized with all values set to 0.
For iteration direction and order, remember with bottom-up we start at the base cases.
Therefore we will start iterating from the end of the input and with only 1 transaction remaining.
TC: O(N*K), O(n*k*2)–> O(N*K)
SC: O(N*K), O(n*k*2)–> O(N*K)

189. Rotate Array 🌟

O(N) Time and O(N) space

Create new array
copy the original array
Rotate the array by (i+k)%n.

O(N) Time and O(1) Space

k%=nums.size(), because if k>n so we need to do only k%n operations.
reverse the array.
reverse the first k elements.
reverse the rest of the array.

190. Reverse Bits 🌟

Using lsb

n&1 will give us lsb.
we will shift lsb to left by 31-i bits and it will be our reverseLsb.
we will or reverseLsb with result.
shift n by 1 to right.
Reference Video

191. Number of 1 Bits 🌟

Using __builtin_popcount

Using n=n&(n-1) trick

Each time of “n &= n - 1”, we delete one ‘1’ from n.

READ:

198. House Robber 🌟🌟

Dynamic Programming

We can rob current house or not rob the current house.
If we rob the current house then amount will be current house amount + i-2th house amount.
else the amount will be i-1th house amount.
we can choose whichever is maximum

Reduced space complexity DP.

There are only two choices for the robber, either he rob the i the house or he don’t.
So the maximum he can rob is rob(i) = max(rob(i-1), rob(i-2) + nums[i])
in the below code we store rob(i-1) in prev1 and rob(i-2) in prev2.

199. Binary Tree Right Side View 🌟🌟

This question is in continuation with A general approach to level order traversal questions series.

Previous Questions

Both solutions passed with 0ms runtime.

Recursive Solution

Simple DFS with right node first.
if our level is same as result vector’s size, then we push the value in the result vector.
Travel right first and then left.

Iterative Solution

We push last element of queue in the result to get right side view.