Leetcode Problem 400-499

402. Remove K Digits 🌟🌟

404. Sum of Left Leaves 🌟

Simple recursive dfs

We want sum of left leaf nodes only, so we can take additional boolean variable to specify whether it is left or not.
we recursively go to left and right leaf node, if leaf node is left then we return its value else return 0.
return dfs for left and right of tree.
Time Complexity: O(n), we traverse the tree once
Space Complexity: O(1) if we don’t consider recursion stack, O(height-of-tree) if we do.

413. Arithmetic Slices 🌟🌟

Here array is arithmetic if it consists of at least three elements ****and if the difference between any two consecutive elements is the same.
We will be using the sliding window technique, comparing 3 elements at a time and then storing the answer in dp array.
Start our loop from 3rd element and compare it with the previous 2 and if there is more than 3 elements with the same difference then we’ll also add that to our dp.
Let’s take an example:

	array: [1,2,3,4]
	Here first 3 element:   [1,2,3] is arithmetic -> count=1
	also next 3 element:    [2,3,4] is arithmetic -> count=1
	now all together:     [1,2,3,4] is arithmetic -> count=1

So while storing 2nd ans in dp, we’ll simply add the previous 1 to our current dp. dp[i] = 1 + dp[i-1]
Add the current dp count to our answer variable, count += dp[i];
Time complexity: O(n).

429. N-ary Tree Level Order Traversal 🌟🌟

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

Previous Questions

Recursive solution

The algorithm is same as the first question in the series, except that we traverse all the children of the root node, not just left and right.

Iterative solution

The algorithm is same as the first question in the series, except that we push all the children of the root node in queue, not just left and right.

438. Find All Anagrams in a String 🌟🌟

sliding window + hashmap

We can maintain a sliding window of size equal to p.size() and check if window == p.
We need to use hashmap not hashset because we need to keep track of duplicate counts.
TC: O(N), N is the length of the string s.
SC: O(N), extra hashmap.

sliding window + array [constant space]

Since in the question it is given that input string has only lowercase letters, we can use a 26-element array to represent the sliding window.Hence the space complexity will be O(26)–>O(1).
TC: O(N), N is the length of the string s.
SC: O(1), constant space. O(26).

441. Arranging Coins 🌟

Simulation

We can just simulate the process of building the staircase.
Assume we have k as result, 1+2+...+i = N, then i*(i+1) = 2N => i^2 = N => i = sqrt(N)
Time Complexity: O(sqrt(n))

Binary Search

The problem can be converted into - Find the maximum k such that k*(k+1)/2 <= n.
Time Complexity: O(logN)

Math solution

As we know the number of coins in each staircase are forming an AP Eg :- 1+2+3+...+a = n Sum of all terms of AP :- (1+a)a/2 = n n is given to us in question, we have to find a

===> a ^ 2 + a = 2 n
===> x ^ 2 + a + 1/4 = 2 n +1/4
===> (a + 1/2 ) ^ 2 = 2n + 1/4
===> (a + 0.5) = sqrt( 2n + 1/4 )
===> a = -0.5 + sqrt( 2n + 1/4 )

We have calculated the value of a = -0.5 + sqrt( 2\*n + 1/4 )
Time Complexity: O(1)

448. Find All Numbers Disappeared in an Array 🌟

Brute force

For each number in the range [1,n], check if it is in the array.
If not then add it in the result array.
TC: O(N^2)
SC: O(1)

Sort + search

Sort the array.
Then we can binary search the missing numbers OR linearly compare 2 adjacent numbers.
TC: O(NlogN)
SC: O(1)

Hash set

We can store the value of each number in the array in a hash set.
Then we can iterate over the range [1,n] and check if the number is in the hash set.
TC: O(N)
SC: O(N)

Space-Optimized using In-place modification

We mark the present element as negative.
then we iterate from [1,n] and check if there is number > 0, if its present then we add it in the answer array.
TC: O(N)
SC: O(1)

450. Delete Node in a BST 🌟🌟

Solution

find the key node: there are 3 cases

    if(key < root) -> find in left subtree
    else if(key > root) -> find in right subtree
    else (key==root) -> delete the node

Now delete the node: there are 3 cases

    if leaf node(0 child)  -> delete(node) and return NULL
    else if node having 1 child  -> delete(node) and return the child
    else  (node having 2 children){
      i) find smallest node (leftmost) in the right subtree of the key
      ii) copy the smallest node value with key node
      iii) delete that smallest node from right subtree (as it have only 1 or 0 child)}

Alternative: In the condition of node having 2 children, we can also find largest node (rightmost) of left subtree of the key.

452. Minimum Number of Arrows to Burst Balloons 🌟🌟

Solution

sort the array by ending points i.e.(a[1] < b[1])
if start of first array is greater than the minEnd then increase the count and set minEnd = end of first array.
else set minEnd = min(minEnd, end of first array)
finally, return count + !points.empty()

454. 4Sum II 🌟🌟

Brute force (TLE)

we can count for every quadruplet if their sum is 0;
TC: O(N^4)
SC: O(1)

O(N^3) (TLE)

If we can take reference of 2 sum problem here we can store num4 values in hashmap so we can access them in O(1) time.
TC: O(N^3)
SC: O(N)

O(N^2) Optimized (AC)

we can use hashmap to store a+b and then we can find -(c+d) to get total count.
TC: O(N^2)
SC: O(N)

461. Hamming Distance 🌟

Original Post - 4 Solutions

Converting Binary Form to String/Array & Iterating

The most basic way one could solve this question is by simply taking the number, converting them to binary form’s string / array and iterating over it to find the number of positions at which bits are different.
TC : O(N), where N is the number of bits in the given input numbers
SC : O(N), required to store the input number’s binary form.

Iterating & Comparing each Bit

We can also iterate over each bit of the given numbers manually and then compare the bits at each position.
To check if the ith bit of a number x is set, we can perform - (x >> i) & 1.
If the bit differ at a given position, we increment the count of hamming distance.
TC : O(N), to iterate over each bit of the number.
SC : O(1), No extra space required.

XOR & count bits

We can XOR x and y and count the number of set bits in the result.

To count the number of set bits we can use these inbuilt options:

ans = bitset<32>(Xor).count()
ans = __builtin_popcount(Xor);
ans = popcount(Xor)            // only since C++20

OR below is code to do it manually.
TC : O(N), to iterate over each bit of the number.
SC : O(1), No extra space required.

Brian-Kernighan’s method

We can use Brian Kernighan’s method to count the number of set bits in the XOR of the two numbers.
Take a XOR of x and y.
Clear(unset) the rightmost bit by n & (n - 1) until xor becomes 0 and increment the count each time.
TC : O(K), where K is the hamming distance between given numbers. This assume XOR operation as O(1)
SC : O(1), No extra space required.

💡 Note:

The number of bits N for this problem is fixed to 32. So, strictly speaking, the time complexity of 1st three solutions is O(N) = O(32) = O(1). But to differentiate between time complexities of 1st three and last approach, I have denoted them as O(N).
It’s likely that if you got such a question during an interview, you will probably be expected to come up with an approach similar to this one. This approach performs the least number of loops to find the number of set bits in a number which is equal to the number of set bits in the number itself.

485. Max Consecutive Ones 🌟

Simple iterative solution

492. Construct the Rectangle 🌟

Iterative Solution

Since l >= w always, w will not be larger than sqrt(area).
If we can find w then l = area / w.
We just simulate the process from sqrt(area) to 1, since in the condition it is given that the difference between L and W should be as small as possible.
TC: O(k) where k is the sqrt of the area.
SC: O(1)

Recursive Solution

From above iterative solution, we can also write recursive solution.
TC: O(k) where k is the sqrt of the area.
SC: O(k) because of recursive stack.

493. Reverse Pairs 🌟🌟🌟

Brute force

for every i we check the condition and increment the counter.
Time complexity: O(n^2)
Space complexity: O(1)

Using Merge Sort modification

TC: O(NlogN)
SC: O(N), if we use temp array.
Striver’s Video for detail explanation.