DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Find First and Last Position of Element in Sorted Array

mediumBinary search

Problem statement

You get an array nums sorted in non-decreasing order (values may repeat) and a target. Return a two-element array [first, last]: the index of the first occurrence of target and the index of its last occurrence. If target does not appear, return [-1, -1].

Aim for O(log n) time, even when the target repeats many times.

Examples

Example 1

Input: nums = [1, 3, 3, 3, 6, 9], target = 3

Output: [1, 3]

Explanation: The three 3s occupy indices 1 to 3.

Example 2

Input: nums = [2, 4, 4, 8], target = 5

Output: [-1, -1]

Explanation: 5 is not in the array.

Hints

Approach

Use one binary-search helper that does not stop at the first match.

  1. Write bound(leftmost): a normal binary search on [lo, hi] that, on nums[mid] == target, records mid as a candidate and then keeps searching:
    • to the left (hi = mid - 1) when looking for the first occurrence;
    • to the right (lo = mid + 1) when looking for the last.
  2. Call it once for each side and return both results. If the target is missing, both calls return -1.

Each call is a full O(log n) search, so the total is still O(log n) regardless of how many duplicates there are.

ComplexityTime O(log n)Space O(1)
Python
class Solution:
def searchRange(self, nums: list[int], target: int) -> list[int]:
def bound(leftmost: bool) -> int:
lo, hi, found = 0, len(nums) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] < target:
lo = mid + 1
elif nums[mid] > target:
hi = mid - 1
else:
found = mid # a match; keep looking towards the edge
if leftmost:
hi = mid - 1
else:
lo = mid + 1
return found
return [bound(True), bound(False)]

Follow-up questions

  • Return the number of times target appears, in O(log n).
  • Given a list of (start, end) timestamp queries against a sorted log, answer each query in O(log n).

Frequently asked questions

That is correct but degrades to O(n) when the run of equal values is long, for example an array where every element is the target. The two-search version stays O(log n) in every case.

Given log lines sorted by timestamp, "all lines from second 1700000000" is exactly a first and last position query. Counting how many requests fall on a value is last - first + 1 without scanning them.

Yes. first = lower_bound(target) and last = lower_bound(target + 1) - 1, then check that first is in range and holds the target. In Python, bisect_left and bisect_right give both bounds directly.