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.
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
Solution Idea
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.
Solution Steps
Solution Pseudocode
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
}
Solution 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
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
}
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
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
}
Solution Pseudocode
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
}
Solution 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!
You are given a row-wise sorted 2D matrix and a given integer k, write a program to find whether the integer ‘k’ is present in the matrix or not. The matrix has the following properties: Integers in each row are sorted from left to right and the first integer of each row is greater than the last integer of the previous row.
Given an array X[] with n elements, we need to write a program to find the largest contiguous subarray sum. A subarray of array X[] of length n is a contiguous segment from X[i] through X[j] where 0<= i <= j <= n. Kadane algorithm idea is intuitive, using a single loop and few variables to solve the problem. We can use a similar idea to solve other coding problems.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!