Weekly Coding Questions - W2

Here are this week's questions :)

1) Merge Intervals
We merge two intervals when the end of first interval is greater than or equal to the start of second interval.
Sorting is done because we don't know whether the input is given ascending order of intervals or not.

2) 3Sum
We are sorting the array because

1. It will be easier to avoid the same elements that will make duplicate triplets as we will just check the adjacent element if its same then we move to next element.
2. For the first element we will use for loop, while for finding the second and third element we use two pointer approach similar to binary search algo.

3) Product of Array Except Self

Approach 1 : Use two for loop and for each element calulate the product and store it in array.
Approach 2 : Calculate the total product and use division operation.
Approach 3 : Use Prefix and Suffix array, their product will be the result array.

nums = [1,2,3,4]
prefix product = [1,1,2,6] ( prefix[i] = prefix[i-1]*nums[i-1] )
suffix product = [24,12,4,1] ( suffix[i] = suffix[i+1]*nums[i+1] )
result = [1*24,1*12,2*4,6*1] = [24,12,8,6]

4) Insert Delete GetRandom O(1)

Use map and vector. Insert the elements in vector and store the elements with their index values in map. So, while removing swap the last element with the element to be removed and then update its value in map. For getting random value, apply it on vector.

5) Subarray Sum Equals K

Brute Force

Use two for loops to calculate the sum of subarray and compare it with the value 'k'.
Time Complexity: O(n^2)
Space Complexity: O(1)

Hash Map
The idea here is to maintain a currentSum and check whether currentSum-k is present in map or not for each element. If present then it tells us that there exists a contagious subarray whose sum is equal to k before the current element. And we update the currentSum in map for each element.

[1,2,3,4,5] , k = 9
result arrays = [2,3,4] & [4,5] i.e count = 2

Case at index = 3:

map : 1->1, 3->1, 6->1
currentSum = 10 (nums[0]+nums[1]+nums[2]+nums[3])
target = currentSum - k = 10-9 = 1;
now, target is present in map, so, there exists a subarray whose sum is equal to k, which is, [2,3,4] subarray.
We put currentSum in map.
New map : 1->1, 3->1, 6->1, 10->1

6) Spiral Matrix

Maintain direction variable to tell us in which direction we have to move after each traverse. Use left, right, top and down variable and do according to the problem given.

7) Next Permutation

Next permutation means finding the next pattern in dictionary order. So, the next pattern will always be greater than its previous pattern. So, we have to find the element at which the change will occur,

array = [1, 3, 5, 4, 2]
from right to left, the first element which is smaller than its previous is 3.

now we have to increase the pattern, so we find the element from right to left, which is greater than the element found.

4 is the element which is just greater than 3

we then swap those numbers and reverse the array after the index at which the change occur.

initial array = [1, 3, 5, 4, 2]
change occur at index = 1, element = 3
greater element at index = 3, element = 4
after swapping,
swapped array = [1, 4, 5, 3, 2]
now, reverse the array after index 1,
next permutation = [1, 4, 2, 3, 5]

reverse is done so that we get the smallest next permutation.

8) Container With Most Water

Use two pointers, one from left and other from right, and calculate the area. Now, the pointer which has the smallest height, update it (for left increase, right decrease), and for the pointer which has the largest height don't update it. This works because we are calculating area based on width and height. If we get greater height then we compromise with the width and go with the height.

9) Rotate Image

For solving these kind of questions, always think of Diagonal swapping, transpose, reversing rows and cols.

10) Word Search

We have to search a word in a board matrix, the only possible way of choosing letters is horizontal and vertical, diagonal not allowed. So, this is a type of DFS traversal in which we maintain visited matrix so that we don't traverse the positions again and for each path, here only 4 directions, we traverse and check if a solution is present then we return true or else we backtrack to the previous path. For simplicity, instead of assigning visited matrix, we can update the board element to some other character and revert it back.

11) 3Sum Closest

The idea is same that of 3 sum but here we have to find the sum which is closest to the target. So, the group having the smallest difference will be considered as the final answer.

12) Find the Duplicate Numbe

Sort and check adjacent elements. Other approach is to use Hash map to store the frequency.
Better approach is, traverse the array and use the elements as index and mark the position they will reach to negative of their original value. If we reach a element which is already negative them the index corresponding to it is the duplicate value.

array = [3, 1, 3, 4, 2]
now traversing the array,
index 0: we will mark arr[3] *= -1
new array = [3, 1, 3, -4, 2]
index 1: we will mark arr[1] *= -1
new array = [3, -1, 3, -4, 2]
index 2: we see that arr[3] is already negative, that means
3 is the duplicate value