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):
    return [findLeft(nums, target), findRight(nums, target)]

function findLeft(nums, target):
    left = 0, right = len(nums) - 1, found = -1
    while left <= right:
        mid = (left + right) // 2    // whole-number division
        if nums[mid] == target:
            found = mid
            right = mid - 1          // keep looking LEFT
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return found

function findRight(nums, target):
    left = 0, right = len(nums) - 1, found = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            found = mid
            left = mid + 1           // the ONE changed line: keep looking RIGHT
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return found

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
  • Try [2, 2, 2, 2, 2, 2] with target 2: stopping at the first hit gives index 2, not 0 (first) or 5 (last)

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 (because the list is sorted, the other copies sit in one block right next to the hit, so a hit tells you where the block is but not where it starts or ends). 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