Bounds of a Repeated Value
MediumBinary Search
Problem
You are given an array nums sorted in non-decreasing order and a value target. Return [first, last]: the indices of the first and the last occurrence of target.
If target does not occur, return [-1, -1]. Your algorithm must run in O(log n) time.
Example 1
- Input:
- nums = [2, 4, 4, 4, 9], target = 4
- Output:
- [1, 3]
The 4s start at index 1 and end at index 3.
Example 2
- Input:
- nums = [2, 4, 9], target = 5
- Output:
- [-1, -1]
Example 3
- Input:
- nums = [7], target = 7
- Output:
- [0, 0]
Constraints
- 0 ≤ nums.length ≤ 10^5
- -10^9 ≤ nums[i], target ≤ 10^9
- nums is sorted in non-decreasing order.
Hint
Show the first hint
A plain binary search finds some copy of target. What should happen when it finds one but you want the first?
Walkthrough
How to approach it
01Clarify before coding
- Can target appear many times? Yes, possibly filling the whole array.
- What to return when it is missing? [-1, -1].
- Is O(log n) a hard requirement? Yes, so walking outward from a hit is not allowed.
02Brute force
Scan for the first index equal to target, then scan from the end for the last.
Cost: O(n) time, O(1) space. Finding one copy with binary search and expanding is still O(n) when target fills the array.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.