Difficulty: Easy, Asked-in: Google, Amazon, Microsoft
Key takeaway: This is a good interview problem to learn problem-solving using binary search. We are applying binary search twice to improve the time complexity over the brute force approach.
Given an array of integers sorted in ascending order, write a code to find the first and last position of a given target value.
Input : A = [-1, 1, 2, 2, 2, 5 ,6, 12, 12], target = 2
Output : First Occurrence = 2, Last Occurrence = 4
Input : A = [21, 32, 51, 70, 71], target = 70
Output : First Occurrence = 3, Last Occurrence = 3
The straightforward approach is to traverse the array and track the index of the first and last occurrence of the target. This approach is inefficient because we did not take advantage of the fact that the given array is sorted.
Time and space complexity analysis
We are running a single loop n time and doing an O(1) operation at each iteration. So time complexity = n * O(1) = O(n). We are using constant extra space so that the space complexity would be O(1).
Solution Idea and Steps
Now critical questions are: can we improve the time complexity further? Can we use the sorted order property to enhance the efficiency of searching?
As we already know, searching any element in the sorted array, the idea of binary search works perfectly. It would take O(logn) time to search the target value in the sorted array. But the given problem is a little different from the binary search problem, where we need to search two occurrences of the target element. So how do we modify the standard binary search algorithm to solve it? Think.
The idea is simple: we can use binary search twice to solve the problem. The first binary search is to find the first occurrence of the target and the second binary search is to find the last occurrence of the target. Let’s design an algorithm for both the steps separately.
Binary search for finding the first occurrence
Let's use the iterative binary search! We first initialize the low = 0 and high = n -1 to track the left and right ends. Now we run a loop till low ≤ high:
Now compare the value at mid with the target. The middle element will be the first occurrence in the two situations : 1) target == A[mid] and target > A[mid-1] i.e. when first occurrence is present somewhere in the middle 2) mid == 0 and A[mid] == target i.e. when the first occurrence is present at the first position. In both situations, we return mid-index as the first occurrence.
if ((mid == 0 || A[mid - 1] < target) && A[mid] == target) return mid
Pseudocode to find the first occurrence
Binary search for finding the last occurrence
Similarly, for finding the last occurrence, we also modify the binary search algorithm. We first initialize the low = 0 and high = n - 1 to track the left and right ends during the binary search loop. Now we run a loop till low ≤ high:
if ( (mid == n-1 || A[mid + 1] > target) && A[mid] == target) return mid
Pseudocode to find the last occurrence
Time and space complexity analysis
Inside the function firstLastOccurrence(A, n, target), we are doing some constant extra operations and applying binary search twice. So time complexity = O(1) + time complexity to search the first occurrence + time complexity to search the last occurrence = O(1) + O(logn) + O(logn) = O(log n).
We are using the implementation of iterative binary search, which takes O(1) extra space. So space complexity = O(1)
Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.