Important Array and Binary Search Interview Questions!
Arrays:
Approach:
I know the most immediate thing would come to anyone’s mind after seeing this question is - sorting. But we are not allowed to do it. In interview, we want to do it in O(n) Time Complexity and O(1) Space Complexity.
How can we do that?
We can create three variables count0, count1, and count2 to store the number of zeroes, ones and twos in the array, respectively. After this we can simply put 0s in first count0 positions, 1s in next count1 positions, and 2s in next count2 positions and we are done!
Solution:
Approach:
There are many ways to solve this problem like sorting and comparing elements present at indexes with the indexes. Another approach can be to store all the elements of given array in a set and then check which element is not present in the set. But in interview, we want to do it in O(n) Time Complexity and O(1) Space Complexity.
How can we do that?
We know that sum of numbers from 1 to n is n*(n+1)/2 (Let’s call this totalSum). We can calculate the sum of elements of the given array and just subtract it from totalSum and we are done!
Solution:
Approach:
There are many ways to solve this problem like sorting and then checking which is the first positive missing element. But in interview, we want to do it in O(n) Time Complexity and O(1) Space Complexity.
That is the reason it is tagged LeetCode Hard.
How can we do that?
By positioning all the positive numbers less than n at their correct location, i.e., putting 1 at 0th index, 2 at 1st index and so on and we are done!
Solution:
Binary Search:
Approach:
We can easily solve this problem by traversing over the array and finding the first and last position of the element. But in interview, we want to do it in O(log(n)) Time Complexity and O(1) Space Complexity.
That is the reason it is tagged LeetCode Hard.
How can we do that?
By applying binary search on the array with the required element value, as binary search is going to find its first position and then again applying binary search on the array with the required element value+1 and then subtracting -1 from the answer as that would give us the last index of the required element and we are done!
Solution:
2. Find Minimum in Rotated Sorted Array
Approach:
We can easily solve this problem by traversing over the array and finding the minimum element. But in interview, we want to do it in O(log(n)) Time Complexity and O(1) Space Complexity.
How can we do that?
By applying binary search on the array and repeatedly checking if the number we found is less than its next element (if the element is at an index less than n-1 or 0th element if not) and also less than its previous element (if the element is at an index greater than 0 or (n-1)th element if not) and we are done!
Solution:
3. Find Smallest Letter Greater Than Target
Approach:
We can easily solve this problem by traversing over the array and finding the position of target element and returning the element after it if it is not at (n-1)th position or returning the first element if it is at (n-1)th position. But in interview, we want to do it in O(log(n)) Time Complexity and O(1) Space Complexity.
How can we do that?
By applying binary search on the array and repeatedly checking if the number we found is greater than target element unless we find a smaller one. We also keep a flag variable to check if we ever encounter a number greater than target. We do this so that we can know whether we found out answer, if not, we know out target element is at last position and now we should return the first element and we are done!
Solution:
Finally, like all good things, this article came to an end!
