Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109nums is a non-decreasing array.-109 <= target <= 109Problem Overview: Given a sorted array of integers, return the first and last index where a target value appears. If the target does not exist, return [-1, -1]. The challenge is finding both boundaries efficiently without scanning the entire array.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest solution walks through the array from left to right. Record the first index where the target appears, then keep updating the last index while the value matches. This works because you examine every element once. The downside is performance: the algorithm runs in O(n) time even though the array is sorted. This approach is useful for understanding the problem but wastes the sorted property of the input.
Approach 2: Modified Binary Search for First and Last Position (O(log n) time, O(1) space)
The array is already sorted, so binary search gives a faster solution. Instead of stopping when the target is found, continue searching to locate the boundaries. Run binary search once to find the leftmost occurrence: when you see the target, move the right pointer left to check for earlier matches. Run binary search again to find the rightmost occurrence: when you see the target, move the left pointer right to check for later matches.
This works because binary search repeatedly halves the search space. Each search takes O(log n), and performing it twice still keeps the complexity at O(log n). Only a few pointer variables are used, so space complexity stays O(1). The technique is common in array problems where duplicates exist and you need boundary indices rather than just presence checks.
Recommended for interviews: Interviewers expect the modified binary search solution with O(log n) time. Mentioning the linear scan shows baseline reasoning, but the optimized boundary search demonstrates that you recognize the sorted property and can adapt binary search to locate ranges rather than single elements.
The goal is to use the binary search algorithm to achieve O(log n) time complexity. We perform two separate binary searches:
This solution uses two modified binary searches, one to find the first occurrence of the target and another to find the last occurrence. The code makes sure to continue searching even if the target is found to ensure the first or last position is located.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log n) due to binary search. Space Complexity: O(1) as no extra space is used apart from input and output.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Quick baseline solution or when the array is not guaranteed to be sorted |
| Two Modified Binary Searches (first + last index) | O(log n) | O(1) | Best approach when the array is sorted and duplicates may exist |
BS-3. First and Last Occurrences in Array | Count occurrences in Array • take U forward • 308,402 views views
Watch 9 more video solutions →Practice Find First and Last Position of Element in Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor