Problem Statement
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1].
Examples:
Example 1:
Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]
Explanation: The target 8 appears first at index 3 and lastly at index 4.Example 2:
Input: nums = [5, 7, 7, 8, 8, 10], target = 6
Output: [-1, -1]Example 3:
Input: nums = [5, 7, 7, 8, 8, 10]
Output: [0, 0]Different Approaches
1️⃣ Linear Search (Brute Force) Approach
Intuition
The naive approach to solve this problem would be a linear traversal of the given array. We traverse the array and store the index where the target appears the first time, in both the first and last occurrence variables. We update the last variable when we again encounter an index where value is equal to the target.
Approach
- Declare two variables, first and last, initialized to -1 to store the first and last occurrences of the target value.
- Traverse the array, when the target value is first encountered in the array, store the index in both first and last.
- For subsequent occurrences of the target value, update only the last variable with the current index.
- Store the first and last occurrences in a vector and return that vector as a result.
Dry Run:
Initially:
Target = 8
FirstOccurrence = -1
LastOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5First Iteration:
Target = 8
FirstOccurrence = -1
LastOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
If arr[i] == Target
5 == 8
falseSecond Iteration:
Target = 8
FirstOccurrence = -1
LastOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
If arr[i] == Target
7 == 8
falseThird Iteration:
Target = 8
FirstOccurrence = -1
LastOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
If arr[i] == Target
7 == 8
falseFourth Iteration:
Target = 8
FirstOccurrence = -1
LastOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
If arr[i] == Target
8 == 8
true
If FirstOccurrence == -1
-1 == -1
true
set FirstOccurrence = i
FirstOccurrence = 3
Set SecondOccurrence = i
SecondOccurrence = 3Fifth Iteration:
Target = 8
FirstOccurrence = 3
LastOccurrence = 3
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
If arr[i] == Target
8 == 8
true
If FirstOccurrence == -1
3 == -1
false
Set SecondOccurrence = i
SecondOccurrence = 4Sixth Iteration:
Target = 8
FirstOccurrence = 3
LastOccurrence = 4
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
If arr[i] == Target
10 == 8
falseLoop Termination:
Target = 8
FirstOccurrence = 3
LastOccurrence = 4
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
i
Since i has crossed the bounds of the array.
So Loop will terminate
And return the FirstOccurrence and LastOccurrence.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
// Initialize variables to store first and last occurrences
int first = -1, last = -1;
vector<int> ans;
// Iterate through the array
for (int i = 0; i < nums.size(); i++) {
// Check if current element is the target
if (nums[i] == target) {
if (first == -1)
{
first = i;
}
last = i;
}
}
// Store the results in the answer vector
ans.push_back(first);
ans.push_back(last);
return ans;
}
};
int main()
{
vector<int> nums = {5, 7, 7, 8, 8, 10};
int target = 8;
// Create an instance of the Solution class
Solution sol;
// Function call to find the first and last occurrences
vector<int> result = sol.searchRange(nums, target);
cout << "The first and last occurrences are at indices: "
<< result[0] << " and " << result[1] << "\n";
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N), whereNis the size of the given array. This is because we are performing a linear search through the array to find the first and last occurrences of the target element. - Space Complexity:
O(1), as we are not using any extra space that grows with the input size. We are only using a few additional variables to store indices and results.
2️⃣ Lower Bound and Upper Bound
Intuition:
In this approach, we use the lower bound and upper bound values to get the first and last occurrences of the target element. Lower bound of the target element will provide us index of the first occurrence of the target element. And, upper bound will provide the index of the element just after the last appearance of the target. So, we could return the lower bound and the upper bound - 1, as the first and last occurrences of the target in the given array.
Approach:
For Lower Bound:
- To get the lower bound, use low and high pointers(Binary search approach) initialized with first and last indices.
- Calculate the middle element and compare the values as mentioned in the below two points.
- If the middle element is greater than or equal to target, update it as our possible answer and eliminate the right half by decreasing the high pointer.
- If the middle element is lesser than the target, eliminate the left half.
- Keep following these steps till the low pointer lesser than or equal to the high pointer.
For Upper Bound:
- To get the upper bound, use low and high pointers(Binary search approach initialized with first and last indices.
- Then calculate the middle element and compare the values as mentioned in the below two points.
- If the middle element is greater than target, store it as our possible answer and eliminate the right half by decreasing the high pointer.
- If the middle element is lesser than or equal to target, eliminate the left half.
- Keep following these steps till the low pointer lesser than or equal to the high pointer.
Edge Case:
- In case the lower bound is equal to the size of the array or the value of array at index = lower bound is not equal to the target element, return both the first and last occurrence as -1. As it means that the target is not present in the array.
- Now return the lower bound and (upper bound - 1) as the first and last occurrences of the target element in the given array.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
private:
// Function to find the lower bound of the target
int lowerBound(vector<int> &nums, int target) {
int low = 0, high = nums.size() - 1;
int ans = nums.size();
// Applying binary search algorithm
while(low <= high) {
int mid = (low + high) / 2;
/* If the middle element is greater than
or equal to the target element update
the answer as mid and eliminate the right half */
if(nums[mid] >= target) {
ans = mid;
high = mid - 1;
}
/* If the middle element is smaller than
the target element then we eliminate
the left half */
else {
low = mid + 1;
}
}
return ans;
}
// Function to find the upper bound of the target
int upperBound(vector<int> &nums, int target) {
int low = 0, high = nums.size() - 1;
int ans = nums.size();
// Applying binary search algorithm
while(low <= high) {
int mid = (low + high) / 2;
/* If the middle element is greater than
the target element update the answer
as mid and eliminate the right half */
if(nums[mid] > target) {
ans = mid;
high = mid - 1;
}
/* If the middle element is greater than
or equal to the target element
eliminate the right half */
else {
low = mid + 1;
}
}
return ans;
}
public:
// Function to find the first and last occurrences of the target
vector<int> searchRange(vector<int> &nums, int target) {
// Function call to find the first occurrence (lower bound)
int firstOcc = lowerBound(nums, target);
// Check if the target is present in the array or not
if(firstOcc == nums.size() || nums[firstOcc] != target) return {-1, -1};
// Function call to find the last occurrence (upper bound)
int lastOcc = upperBound(nums, target) - 1;
return {firstOcc, lastOcc};
}
};
int main()
{
vector<int> nums = {5, 7, 7, 8, 8, 10};
int target = 8;
// Create an instance of the Solution class
Solution sol;
// Function call to find the first and last occurrences
vector<int> result = sol.searchRange(nums, target);
cout << "The first and last occurrences are at indices: "
<< result[0] << " and " << result[1] << "\n";
return 0;
}Complexity Analysis:
- Time Complexity:
2*O(log N), whereNis the size of the given array. Both the lowerBound and upperBound functions perform a binary search, which operates in logarithmic time. Thus, the overall time complexity isO(log N). - Space Complexity:
O(1), as we are using a constant amount of extra space regardless of the input size. The space used by the variables low, high, mid, and ans does not depend on the size of the input array.
3️⃣ Binary Search (Optimal) Approach:
Intuition:
The optimal solution of this problem uses binary search to look for the first and last occurrences of the target element. While calculating the first occurrence, keep in mind that every time we get an element equal to target, look for the target again in its left half. Similarly, for getting the last occurrence, keep in mind that when we get an element equal to target, we look for the target again in its right half, so we get the last index where the target appears.
Approach for firstOccurrence():
- Start with taking low and high pointers initialized with the first index, and last index as that would be the search space.
- Calculate the middle element and compare the values as mentioned in the below three points.
- If the middle element of array is equal to target, update it as an possible answer and eliminate the right half by decreasing the high pointer. Then, search in the left half for more smaller index that satisfies the same condition.
- If the middle element is lesser than the target, eliminate the left half.
- If the middle element is greater than the target, eliminate the right half.
- Keep following these steps till the low pointer lesser than or equal to the high pointer.
Dry Run:
Initialization:
Target = 8
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5First Iteration:
Target = 8
Left = 0
Right = 5
Mid = Left + (Right - Left) / 2
= 0 + (5 - 0) / 2
= 0 + 5 / 2 = 2
= 2
FirstOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
Left Mid Right
As, arr[mid] < Target
7 < 8
So, Left = Mid + 1
Left = 2 + 1
Left = 3Second Iteration:
Target = 8
Left = 3
Right = 5
Mid = Left + (Right - Left) / 2
= 3 + (5 - 3) / 2
= 3 + 2 / 2 = 3 + 1
= 4
FirstOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
Left Mid Right
As, arr[mid] == Target
8 == 8
true
FistOccurrence = 4
GO Left
So, Right = Mid - 1
Right = 4 - 1
Right = 3Third Iteration:
Target = 8
Left = 3
Right = 3
Mid = Left + (Right - Left) / 2
= 3 + (3 - 3) / 2
= 3 + 0 / 2 = 3 + 0
= 3
FirstOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
Left
Mid
Right
As, arr[mid] == Target
8 == 8
true
FistOccurrence = 3
GO Left
So, Right = Mid - 1
Right = 3 - 1
Right = 2Loop Termination:
Target = 8
Left = 3
Right = 2
FirstOccurrence = 3
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
Right Left
As Left extends the Right
The loop would terminate
and return FirstOccurrence, which is 3Approach for lastOccurrence():
- Start with taking low and high pointers initialized with the first index, and last index.
- Calculate the middle element and compare the values as mentioned in the below three points.
- If the middle element of the array is equal to target, update it as a possible answer and eliminate the right half by decreasing the high pointer. Then, search in the right half for more greater index that satisfies the same condition.
- If the middle element is lesser than the target, eliminate the left half.
- If the middle element is greater than the target, eliminate the right half.
- Keep following these steps till the low pointer lesser than or equal to the high pointer.
Dry Run:
Initialization:
Target = 8
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5First Iteration:
Target = 8
Left = 0
Right = 5
Mid = Left + (Right - Left) / 2
= 0 + (5 - 0) / 2
= 0 + 5 / 2 = 2
= 2
LastOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
Left Mid Right
As, arr[mid] < Target
7 < 8
So, Left = Mid + 1
Left = 2 + 1
Left = 3Second Iteration:
Target = 8
Left = 3
Right = 5
Mid = Left + (Right - Left) / 2
= 3 + (5 - 3) / 2
= 3 + 2 / 2 = 3 + 1
= 4
LastOccurrence = -1
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
Left Mid Right
As, arr[mid] == Target
8 == 8
true
LastOccurrence = 4
GO Right
So, Left = Mid + 1
Left = 4 + 1
Left = 5Third Iteration:
Target = 8
Left = 5
Right = 5
Mid = Left + (Right - Left) / 2
= 5 + (5 - 5) / 2
= 5 + 0 / 2 = 5 + 0
= 5
LastOccurrence = 4
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
Left
Mid
Right
As, arr[mid] > Target
10 == 8
true
GO Left
So, Right = Mid - 1
Right = 5 - 1
Right = 4Loop Termination:
Target = 8
Left = 5
Right = 4
LastOccurrence = 4
+-----+-----+-----+-----+-----+-----+
arr = | 5 | 7 | 7 | 8 | 8 | 10 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
Right Left
As Left extends the Right
The loop would terminate
and return LastOccurrence, which is 4Code:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
private:
// Function to find the first occurrence of the target
int firstOccurrence(vector<int> &nums, int target) {
int low = 0, high = nums.size() - 1;
int first = -1;
// Applying Binary Search Algorithm
while(low <= high) {
int mid = low + (high - low) / 2;
/* If the target element is found, we
update the first variable to mid and
eliminate the right half to look for
more smaller index where target is present */
if(nums[mid] == target) {
first = mid;
high = mid - 1;
}
/* If middle element is smaller,
we eliminate the left half */
else if(nums[mid] < target) {
low = mid + 1;
}
/* If middle element is greater,
we eliminate the right half */
else {
high = mid - 1;
}
}
return first;
}
// Function to find the last occurrence of the target
int lastOccurrence(vector<int> &nums, int target) {
int low = 0, high = nums.size() - 1;
int last = -1;
// Applying Binary Search Algorithm
while(low <= high) {
int mid = low + (high - low) / 2;
/* If the target element is found, we
update the first variable to mid and
eliminate the right half to look for
more greater index where target is present */
if(nums[mid] == target) {
last = mid;
low = mid + 1;
}
/* If middle element is smaller,
we eliminate the left half */
else if(nums[mid] < target) {
low = mid + 1;
}
/* If middle element is greater,
we eliminate the right half */
else {
high = mid - 1;
}
}
return last;
}
public:
// Function to find the first and last occurrences of the target
vector<int> searchRange(vector<int> &nums, int target) {
// Function call to find the first occurence of target
int first = firstOccurrence(nums, target);
// If the target is not present in the array
if(first == -1) return {-1, -1};
// Function call to find the last occurence of target
int last = lastOccurrence(nums, target);
return {first, last};
}
};
int main()
{
vector<int> nums = {5, 7, 7, 8, 8, 10};
int target = 8;
// Create an instance of the Solution class
Solution sol;
// Function call to find the first and last occurrences
vector<int> result = sol.searchRange(nums, target);
cout << "The first and last occurrences are at indices: "
<< result[0] << " and " << result[1] << "\n";
return 0;
}Complexity Analysis:
- Time Complexity:
O(log N), where N is the size of the given array. Both the firstOccurrence and lastOccurrence functions perform a binary search, which operates in logarithmic time. Thus, the overall time complexity is O(log N). - Space Complexity:
O(1), as we are using a constant amount of extra space regardless of the input size. The space used by the variables low, high, mid, first, and last does not depend on the size of the input array.
Complete Code:
class Solution {
public:
// Function to find the first and last occurrence of 'target' in a sorted array 'nums'
vector<int> searchRange(vector<int> &nums, int target) {
int left = 0; // Initialize left pointer to the start of the array
int right = nums.size() - 1; // Initialize right pointer to the end of the array
int firstOccurrence = -1; // Default value if first occurrence is not found
int lastOccurrence = -1; // Default value if last occurrence is not found
// Binary search to find the first occurrence of 'target'
while(left <= right) {
int mid = left + (right - left) / 2; // Calculate mid-point to avoid overflow
if(nums[mid] == target) { // If mid element equals 'target'
firstOccurrence = mid; // Update firstOccurrence to current mid index
right = mid - 1; // Move to the left half to find the first occurrence
} else if(nums[mid] > target) { // If mid element is greater than 'target'
right = mid - 1; // Move to the left half
} else { // If mid element is less than 'target'
left = mid + 1; // Move to the right half
}
}
// Reset left and right pointers to search for the last occurrence of 'target'
left = 0;
right = nums.size() - 1;
// Binary search to find the last occurrence of 'target'
while(left <= right) {
int mid = left + (right - left) / 2; // Calculate mid-point to avoid overflow
if(nums[mid] == target) { // If mid element equals 'target'
lastOccurrence = mid; // Update lastOccurrence to current mid index
left = mid + 1; // Move to the right half to find the last occurrence
} else if(nums[mid] > target) { // If mid element is greater than 'target'
right = mid - 1; // Move to the left half
} else { // If mid element is less than 'target'
left = mid + 1; // Move to the right half
}
}
return {firstOccurrence, lastOccurrence}; // Return the indices of the first and last occurrence
}
};