#34
Find First and Last Position of Element in Sorted Array
Medium Lower & upper bound
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the first and last index of target in a sorted array, or [-1, -1], in O(log n).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the first and last index of target.
Why this works: lowerBound(x) gives the first index with value ≥ x. First = lowerBound(target), last = lowerBound(target + 1) - 1.
Example: [5, 7, 7, 8, 8, 10], target 8
lowerBound(8) = 3lowerBound(9) = 5 → last 4[3, 4]
✦Hints open one at a time
Run binary search twice.
First search: when you find target, keep going left. Second: keep going right.
↗Approach
Write one helper "first index with value >= x" (lower bound). first = lb(target), last = lb(target + 1) − 1. Check that first is in range and holds target.
</>Solution (Java)
class Solution {
public int[] searchRange(int[] nums, int target) {
int first = lowerBound(nums, target);
if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
int last = lowerBound(nums, target + 1) - 1;
return new int[]{first, last};
}
// first index whose value is >= x (nums.length if none)
private int lowerBound(int[] nums, int x) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}
}!Common mistake
Finding one occurrence and then walking left/right linearly — O(n) when the value repeats a lot.
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon