Find First and Last Position of Element in Sorted Array

Problem

Given a sorted array of integers and a target value, return the starting and ending index of the target's run - [first, last] - or [-1, -1] if the target does not appear. The array may contain duplicates, and the solution must run in O(log n).

Example 1:

Input: nums = [1, 3, 4, 4, 4, 9], target = 4
Output: [2, 4]
Explanation: the value 4 occupies indices 2, 3, and 4.

Example 2:

Input: nums = [1, 3, 4, 4, 4, 9], target = 5
Output: [-1, -1]
Explanation: 5 does not appear.

Example 3:

Input: nums = [8, 8, 8], target = 8
Output: [0, 2]
Explanation: every element matches, so the run spans the whole array.

Constraints:

• 0 <= nums.length <= 10^4
• -100 <= nums[i] <= 100 (non-decreasing order)
• -100 <= target <= 100

Solution Breakdown

Approach - two boundary binary searches: the leftmost index holding the target, and the leftmost index holding anything greater, minus one.

Exact-match binary search is the wrong template here: it returns the first mid that happens to equal the target, which can land anywhere inside a run of duplicates. The boundary variant changes the contract - instead of "return on match", it keeps mid in the window whenever mid may still be the answer. For the left boundary, hi = mid on nums[mid] >= target (discarding only indices that are provably too far right); for the right boundary, the same idea mirrored.

The implementation collapses both searches into one helper by exploiting the run structure: leftmost(t) returns the first index where nums[i] >= t. The left boundary is leftmost(target). The right boundary is the element just before the next run starts - leftmost(target + 1) - 1 - because the run is exactly the stretch of indices holding values that are >= target but < target + 1. One verification closes the loop: if left is past the end or nums[left] != target, the target is absent and [-1, -1] is the answer; otherwise the right search is guaranteed to land inside the run, so no second check is needed.

Trace target 4 on [1, 3, 4, 4, 4, 9], with the helper's exclusive bounds lo, hi = 0, len(nums): leftmost(4) - mid=3, nums[3] = 4 >= 4, keep it, hi = 3; mid=1, nums[1] = 3 < 4, lo = 2; mid=2, nums[2] = 4 >= 4, hi = 2; window is [2, 2], left = 2. leftmost(5) - mid=3, 4 < 5, lo = 4; mid=5, nums[5] = 9 >= 5, hi = 5; mid=4, 4 < 5, lo = 5; window is [5, 5], so right = 5 - 1 = 4. Answer [2, 4], matching the run at indices 2, 3, 4.

Edge cases - an empty array fails the left == len(nums) check and returns [-1, -1] without indexing. A target past the end converges to left == len(nums); a target between values converges to an insertion point where nums[left] != target. A single match, [2, 6, 10, 14] with target 14, returns [3, 3]: leftmost(15) runs off the end to 4, and 4 - 1 = 3.

Complexity - two binary searches, O(log n) each, O(1) space. The sort is given, not performed; the whole value of the O(log n) bound is lost the moment you linear-scan for the boundaries.