Difficulty: Easy, Asked in: Google, Amazon, Microsoft
Key takeaway: This is an excellent interview problem to learn problem-solving using binary search. We apply binary search twice to improve the time complexity over a brute force approach.
Given an array of integers sorted in ascending order, write 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.
vector<int> firstLastOccurence(int A[], int n, int target)
{
vector<int> firstLast = {-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;
}
def first_last_occurence(A, n, target):
first_last = [-1, -1]
for i in range(n):
if A[i] == target:
if first_last[0] == -1:
first_last[0] = i
first_last[1] = i
return first_last
We are running a single loop n time and doing O(1) operations at each iteration. Time complexity = n * O(1) = O(n). We are using constant extra space, so space complexity = O(1).
Now the 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, binary search works perfectly for searching for any element in the sorted array. It would take O(logn) time to search for the target value. But the given problem is different from the binary search problem, where we need to search for 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 for finding the first occurrence of the target, and the second binary search is for finding the last occurrence of the 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:
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, to find the last occurrence, we also modify the binary search algorithm. We first initialize low = 0 and high = n - 1 to track the left and right ends during the binary search loop. Now we run a loop until low ≤ high:
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 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 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;
}
vector<int> findFirstLastOccurrence(int A[], int n, int target)
{
vector<int> firstLast = {-1, -1};
firstLast[0] = findFirstOccurrence(A, n, target);
firstLast[1] = findLastOccurrence(A, n, target);
return firstLast;
}
def find_last_occurrence(A, n, target):
low = 0
high = n - 1
while low <= high:
mid = low + (high - low) // 2
if (mid == n - 1 or A[mid + 1] > target) and A[mid] == target:
return mid
elif target < A[mid]:
high = mid - 1
else:
low = mid + 1
return -1
def find_first_occurrence(A, n, target):
low = 0
high = n - 1
while low <= high:
mid = low + (high - low) // 2
if (mid == 0 or A[mid - 1] < target) and A[mid] == target:
return mid
elif target > A[mid]:
low = mid + 1
else:
high = mid - 1
return -1
def find_first_last_occurrence(A, n, target):
first_last = [-1, -1]
first_last[0] = find_first_occurrence(A, n, target)
first_last[1] = find_last_occurrence(A, n, target)
return first_last
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 for his contribution in creating the first version of this content. If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!