Difficulty: Easy, Asked-in: Google, Amazon, Microsoft
Key takeaway: This is an excellent interview problem to learn problem-solving using binary search. We are applying binary search twice to improve the time complexity over 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.
Example 1
Input : A[] = [-1, 1, 2, 2, 2, 5 ,6, 12, 12], target = 2
Output : First occurrence = 2, Last occurrence = 4
Example 2
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 index of the first and last occurrence of target. This approach is inefficient because we did not take advantage of the fact that given array is sorted.
int[] firstLastOccurence(int A[], int n, int target)
{
int firstLast[2] = [-1, -1]
for (int i = 0; i < n; i = i + 1)
{
if (A[i] == target)
{
if (firstLast[0] = -1)
firstLast[0] = i
firstLast[1] = i
}
}
return firstLast
}
We are running a single loop n time and doing O(1) operation at each iteration. Time complexity = n * O(1) = O(n). We are using constant extra space, so space complexity = O(1).
Now critical questions are: Can we improve the time complexity further? Can we use the sorted order property to enhance efficiency of searching?
As we already know,binary search works perfectly for searching any element in the sorted array. It would take O(logn) time to search the target value. But the given problem is 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 for finding the first occurrence of target and the second binary search for finding the last occurrence of target. Let’s design an algorithm for both steps separately.
Let's use iterative binary search! We first initialize 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 target. The middle element will be the first occurrence in 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 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
int findFirstOccurrence(int A[], int n, int target)
{
int low = 0, high = n - 1
while (low <= high)
{
int mid = low + (high - low)/2
if ((mid == 0 || A[mid - 1] < target) && A[mid] == target)
return mid
else if (target > A[mid])
low = mid + 1
else
high = mid - 1
}
return -1
}
Similarly, for finding the last occurrence, we also modify binary search algorithm. We first initialize low = 0 and high = n - 1 to track left and right ends during binary search loop. Now we run a loop till low ≤ high:
if ( (mid == n - 1 || A[mid + 1] > target) && A[mid] == target)
return mid
int findLastOccurrence(int A[], int n, int target)
{
int low = 0, high = n - 1
while (low <= high)
{
int mid = low + (high - low)/2
if ((mid == n - 1 || A[mid + 1] > target) && A[mid] == target)
return mid
else if (target < A[mid])
high = mid - 1
else
low = mid + 1
}
return -1
}
int[] findFirstLastOccurrence(int A[], int n, int target)
{
int firstLast[2] = [-1, -1]
firstLast[0] = findFirstOccurrence(A, n, target)
firstLast[1] = findLastOccurrence(A, n, target)
return firstLast
}
Inside the function firstLastOccurrence(A[], n, target), we are doing some constant extra operations and applying binary search twice. Time complexity = O(1) + Time complexity to search first occurrence + Time complexity to search 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. Space complexity = O(1)
Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.