You're given an array of integers nums, sorted in non-decreasing order, and an integer target.
Return the starting and ending positions of target in nums as an array [first, last] — the index of its first occurrence and the index of its last occurrence.
If target does not appear in nums, return [-1, -1].
Your algorithm must run in O(log n) time.
O(log n) — what family of algorithms does that combination always point to?lowerBound(x) returning the first index with nums[i] >= x. Then first = lowerBound(target) and last = lowerBound(target + 1) - 1.lowerBound(target + 1) is the first index whose value is strictly greater than target. Since all copies of target sit in one contiguous block (the array is sorted), that index is exactly one slot past the block — step back one and you're on the last copy.8), you'd expand across the whole array — O(n), exactly what the statement forbids. The boundary search stays O(log n) no matter how wide the block is.n — one slot past the end. That's why the absence check first == n must run before reading nums[first]; it also gracefully covers the empty-array case.target is at most 10^9, and 10^9 + 1 fits comfortably in every language's integer type used by the solutions. In stricter settings, an explicit upperBound helper avoids the addition entirely.count = last - first + 1, or equivalently lowerBound(target + 1) - lowerBound(target) — no extra passes needed.nums[mid] <= x and the helper returns the first index with a value strictly greater than x. Then last = upperBound(target) - 1. Same template, one flipped comparison.mid against the ends), then run the boundary searches inside the correct half — still O(log n) overall. That's the Search in Rotated Sorted Array pattern.std::lower_bound and std::upper_bound, and the pair of edges together is literally called std::equal_range.Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] The value 8 first appears at index 3 and last appears at index 4.
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] 6 is not in the array, so both positions are -1.
Input: nums = [], target = 0 Output: [-1,-1] An empty array contains nothing — return [-1, -1].
- 0 <= nums.length <= 10^5 - -10^9 <= nums[i] <= 10^9 - nums is sorted in non-decreasing order - -10^9 <= target <= 10^9
A sorted array plus an explicit O(log n) demand — binary search is calling. But there's a twist: with duplicates, a standard binary search finds an occurrence, not the first or the last. This problem teaches the boundary-search template — the single most reusable binary-search skill you'll ever learn.
O(log n).lo and hi mean at every step is what keeps boundary searches free of off-by-one bugs.In plain words: target may appear zero, one, or many times. Because nums is sorted, all its copies sit in one contiguous block. Report the block's two ends — or [-1, -1] if the block doesn't exist.
Formally: return [min i, max i] over all i with nums[i] == target, or [-1, -1] if no such i exists, in O(log n) time.
Worked example — nums = [5,7,7,8,8,10], target = 8
index: 0 1 2 3 4 5
nums: 5 7 7 8 8 10
^ ^
first last
answer: [3, 4]
Asking two or three sharp questions before coding shows you think about contracts, not just code.
“Is the array guaranteed to be sorted, and can it contain duplicates?”
Yes — non-decreasing. Duplicates are the whole point: they are why first and last can differ. Without sortedness, binary search is off the table.
“Can the array be empty?”
Yes — nums.length can be 0, and the answer is then [-1, -1]. Your code must not index into an empty array.
“What if the target appears exactly once?”
Then first == last — e.g. searching for 10 above returns [5, 5].
“What if every element equals the target?”
The block spans the whole array: [0, n - 1]. This case is exactly what kills the find-then-expand shortcut.
“How large can n get, and is O(n) acceptable?”
Up to 10^5 — a linear scan would run fast enough, but the statement explicitly requires O(log n), so binary search is the expected answer.
Before I code, a few quick checks.
The array is sorted non-decreasing and may contain duplicates — that is exactly why the first and last positions can differ, correct?
If the target is missing, or the array is empty, I return [-1, -1].
Since you require O(log n), I will run two boundary binary searches — one for the left edge of the block, one for the right.
With duplicates, a standard binary search stops at whichever copy mid happens to hit — you have no idea whether it is the first, the last, or one in the middle.
nums = [8, 8, 8, 8, 8], target = 8 standard search → mid = 2 → found! ...but first is 0, last is 4
To find the first occurrence, treat a match like too big: when nums[mid] >= target, pull hi down to mid and keep searching left. The window collapses onto the left edge of the block. Matches guide the search; they never end it.
Define lowerBound(x) = the first index with nums[i] >= x. Then:
first = lowerBound(target) last = lowerBound(target + 1) - 1
The first index that is at least target + 1 sits just past the block of targets — step back one and you are on the last copy. Writing one careful helper and calling it twice halves your surface area for bugs.
| Linear scan | Two binary searches | |
|---|---|---|
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
Full, runnable code for both — in all four languages — lives in the Approaches selector below.
Key takeaway
When a sorted array has duplicates, binary search for boundaries, not matches. One helper — lowerBound(x), the first index with value at least x — answers both edges: first = lowerBound(target), last = lowerBound(target + 1) - 1. This boundary template powers every first/last position where a condition flips problem.
lowerBound(x):
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] < x: lo = mid + 1
else: hi = mid
return lo
first = lowerBound(target)
if first == n or nums[first] != target: return [-1, -1]
return [first, lowerBound(target + 1) - 1]