Find First and Last Position

Difficulty: Medium

Problem

A librarian keeps books on a shelf ordered by catalog number (non-decreasing), and wants the first and last slot holding a particular number, target. Given the sorted integer array nums, return those two indices as [first, last], or [-1, -1] if target is absent. Your solution has to run in O(log n) time.

Example

Input: nums = [1, 2, 2, 2, 4, 6, 6], target = 2
Output: [1, 3]
Explanation: 2 first appears at index 1 and last appears at index 3.

Brute-force approach

Scan the array from left to right to find the first occurrence, then scan from right to left (or continue forward) to find the last occurrence.

Steps

  1. Scan left to right to find the first index where nums[i] == target
  2. Scan right to left to find the last index where nums[i] == target
  3. If not found in either scan, return [-1, -1]

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Scans the entire array in the worst case, O(n)
  • Doesn't use the sorted property at all
  • Two full passes through the array

Optimal approach

Key insight: Standard binary search stops when it finds the target. To find the FIRST occurrence, keep searching LEFT even after finding it. To find the LAST, keep searching RIGHT.

Run two binary searches: one modified to find the leftmost (first) occurrence and another to find the rightmost (last) occurrence of the target.

Steps

  1. findLeft: Binary search where matches push search LEFT
  2. findRight: Binary search where matches push search RIGHT
  3. Return [findLeft, findRight]

Time complexity: O(log n) · Space complexity: O(1)

Pseudocode

function searchRange(nums, target):
    left = findLeft(nums, target)
    right = findRight(nums, target)
    return [left, right]

function findLeft(nums, target):
    lo = 0, hi = len(nums) - 1, result = -1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if nums[mid] == target:
            result = mid
            hi = mid - 1
        else if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

Hints

  • Use two separate binary searches: one for the leftmost occurrence and one for the rightmost
  • When finding the leftmost: even when you find the target, keep searching left
  • When finding the rightmost: even when you find the target, keep searching right

Complexity questions

What is the time complexity of linear scan for first and last positions?

O(n). We may scan the entire array in both passes, O(n) total.

What is the time complexity of two binary searches?

O(log n). Two binary searches: O(log n) + O(log n) = O(2 log n) = O(log n).

What is the space complexity?

O(1). Only a few variables used: O(1) space.

Check your understanding of Find First and Last Position

For nums = [1, 2, 2, 2, 3], target = 2, what are the first and last positions?

[1, 3]. The value 2 first appears at index 1 and last appears at index 3. So the answer is [1, 3].

Why can't we use a single binary search to solve this?

A single binary search finds ANY occurrence, not necessarily the first or last. Standard binary search stops at the first match it finds, which could be anywhere in the range of duplicates. We need two specialized searches: one that keeps going left after finding a match, and one that keeps going right.

If the target appears only once, what should the output be?

[index, index] where index is the target's position. If the target appears once at index i, it is both the first and last occurrence. Return [i, i].

Related problems

Keep practising