Find First and Last Position
Difficulty: Medium
Problem
A librarian keeps books on a shelf ordered by catalog number (non-decreasing), and wants the first and last slot holding a particular number, target. Given the sorted integer array nums, return those two indices as [first, last], or [-1, -1] if target is absent. Your solution has to run in O(log n) time.
Example
Input: nums = [1, 2, 2, 2, 4, 6, 6], target = 2
Output: [1, 3]
Explanation: 2 first appears at index 1 and last appears at index 3.
Brute-force approach
Scan the array from left to right to find the first occurrence, then scan from right to left (or continue forward) to find the last occurrence.
Steps
- Scan left to right to find the first index where nums[i] == target
- Scan right to left to find the last index where nums[i] == target
- If not found in either scan, return [-1, -1]
Time complexity: O(n) · Space complexity: O(1)
Trade-offs
- Scans the entire array in the worst case, O(n)
- Doesn't use the sorted property at all
- Two full passes through the array
Optimal approach
Key insight: Standard binary search stops when it finds the target. To find the FIRST occurrence, keep searching LEFT even after finding it. To find the LAST, keep searching RIGHT.
Run two binary searches: one modified to find the leftmost (first) occurrence and another to find the rightmost (last) occurrence of the target.
Steps
- findLeft: Binary search where matches push search LEFT
- findRight: Binary search where matches push search RIGHT
- Return [findLeft, findRight]
Time complexity: O(log n) · Space complexity: O(1)
Pseudocode
function searchRange(nums, target):
return [findLeft(nums, target), findRight(nums, target)]
function findLeft(nums, target):
left = 0, right = len(nums) - 1, found = -1
while left <= right:
mid = (left + right) // 2 // whole-number division
if nums[mid] == target:
found = mid
right = mid - 1 // keep looking LEFT
else if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return found
function findRight(nums, target):
left = 0, right = len(nums) - 1, found = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
found = mid
left = mid + 1 // the ONE changed line: keep looking RIGHT
else if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return found
Hints
- Use two separate binary searches: one for the leftmost occurrence and one for the rightmost
- When finding the leftmost: even when you find the target, keep searching left
- When finding the rightmost: even when you find the target, keep searching right
- Try [2, 2, 2, 2, 2, 2] with target 2: stopping at the first hit gives index 2, not 0 (first) or 5 (last)
Complexity questions
What is the time complexity of linear scan for first and last positions?
O(n). We may scan the entire array in both passes, O(n) total.
What is the time complexity of two binary searches?
O(log n). Two binary searches: O(log n) + O(log n) = O(2 log n) = O(log n).
What is the space complexity?
O(1). Only a few variables used: O(1) space.
Check your understanding of Find First and Last Position
For nums = [1, 2, 2, 2, 3], target = 2, what are the first and last positions?
[1, 3]. The value 2 first appears at index 1 and last appears at index 3. So the answer is [1, 3].
Why can't we use a single binary search to solve this?
A single binary search finds ANY occurrence, not necessarily the first or last. Standard binary search stops at the first match it finds, which could be anywhere in the range of duplicates (because the list is sorted, the other copies sit in one block right next to the hit, so a hit tells you where the block is but not where it starts or ends). We need two specialized searches: one that keeps going left after finding a match, and one that keeps going right.
If the target appears only once, what should the output be?
[index, index] where index is the target's position. If the target appears once at index i, it is both the first and last occurrence. Return [i, i].
Related problems
- Binary Search (Easy)
- Search Insert Position (Easy)
- Search in Rotated Sorted Array (Medium)