LeetCode 34: Find First and Last Position of Element in Sorted Array

Problem Restatement

We are given an integer array nums sorted in non-decreasing order and an integer target.

We need to find the first and last index where target appears.

If target does not appear in the array, return:

[-1, -1]

The required runtime is O(log n), so we should use binary search instead of scanning the array. The array length can be 0, and nums is sorted in non-decreasing order.

Input and Output

Function shape:

def searchRange(nums: list[int], target: int) -> list[int]:
    ...

Examples

Example 1:

nums = [5, 7, 7, 8, 8, 10]
target = 8

The value 8 appears at indices 3 and 4.

Return:

[3, 4]

Example 2:

nums = [5, 7, 7, 8, 8, 10]
target = 6

The value 6 does not appear.

Return:

[-1, -1]

Example 3:

nums = []
target = 0

The array is empty.

Return:

[-1, -1]

First Thought: Linear Search

The simplest approach is to scan the array.

When we first see target, record that index as first.

Keep scanning until the end. Every time we see target, update last.

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        first = -1
        last = -1

        for i, num in enumerate(nums):
            if num == target:
                if first == -1:
                    first = i
                last = i

        return [first, last]

This is correct, but it takes O(n) time.

Problem With Linear Search

The problem requires O(log n) runtime.

A full scan does not use the fact that nums is sorted.

Since all occurrences of target are grouped together in a sorted array, we can find the boundaries with binary search.

We need two searches:

1. Find the first index where nums[i] >= target.
2. Find the first index where nums[i] > target.

The first position is the left boundary.

The second position is one step after the right boundary.

Key Insight

Instead of searching only for equality, search for insertion positions.

For this array:

nums = [5, 7, 7, 8, 8, 10]
target = 8

The first index where the value is greater than or equal to 8 is index 3.

[5, 7, 7, 8, 8, 10]
          ^

The first index where the value is greater than 8 is index 5.

[5, 7, 7, 8, 8, 10]
                ^

So the answer is:

[3, 5 - 1] = [3, 4]

This boundary-search style is often cleaner than trying to stop when nums[mid] == target.

Algorithm

Write a helper function:

lower_bound(x)

It returns the first index i such that:

nums[i] >= x

If every number is smaller than x, it returns len(nums).

Then:

left = lower_bound(target)
right = lower_bound(target + 1) - 1

But to avoid relying on target + 1, we can write a second boundary search for the first index where:

nums[i] > target

This works even at integer limits.

So the plan is:

1. Find left, the first index with nums[i] >= target.
2. If left == len(nums) or nums[left] != target, return [-1, -1].
3. Find right_plus_one, the first index with nums[i] > target.
4. Return [left, right_plus_one - 1].

Correctness

Because nums is sorted, all values smaller than target appear before all values equal to target.

So the first index where nums[i] >= target is exactly the first possible position of target.

If this index is outside the array, or if nums[left] is not equal to target, then target does not appear anywhere in the array.

If target appears, all copies of target form one continuous block.

The first index where nums[i] > target is the first position after that block.

Therefore, the last index containing target is:

right_plus_one - 1

So the algorithm returns exactly the first and last positions of target.

Complexity

Implementation

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def first_greater_or_equal(x: int) -> int:
            left = 0
            right = len(nums)

            while left < right:
                mid = left + (right - left) // 2

                if nums[mid] >= x:
                    right = mid
                else:
                    left = mid + 1

            return left

        def first_greater(x: int) -> int:
            left = 0
            right = len(nums)

            while left < right:
                mid = left + (right - left) // 2

                if nums[mid] > x:
                    right = mid
                else:
                    left = mid + 1

            return left

        left = first_greater_or_equal(target)

        if left == len(nums) or nums[left] != target:
            return [-1, -1]

        right = first_greater(target) - 1

        return [left, right]

Code Explanation

The helper first_greater_or_equal searches a half-open range:

[left, right)

At the start:

left = 0
right = len(nums)

This allows the function to return len(nums) when no valid index exists.

For each middle index:

mid = left + (right - left) // 2

If nums[mid] >= x, then mid may be the answer, so we keep the left half including mid.

right = mid

Otherwise, nums[mid] < x, so mid cannot be the answer.

left = mid + 1

The second helper first_greater has the same shape, but its condition is:

nums[mid] > x

After finding the left boundary:

left = first_greater_or_equal(target)

we check whether target actually exists:

if left == len(nums) or nums[left] != target:
    return [-1, -1]

Then the right boundary is one index before the first number greater than target.

right = first_greater(target) - 1

Return both boundaries.

Testing

def check(nums: list[int], target: int, expected: list[int]) -> None:
    actual = Solution().searchRange(nums, target)
    assert actual == expected, (nums, target, actual, expected)

def run_tests():
    check([5, 7, 7, 8, 8, 10], 8, [3, 4])
    check([5, 7, 7, 8, 8, 10], 6, [-1, -1])
    check([], 0, [-1, -1])
    check([1], 1, [0, 0])
    check([1], 0, [-1, -1])
    check([2, 2, 2, 2], 2, [0, 3])
    check([1, 2, 3, 4, 5], 3, [2, 2])
    check([1, 2, 3, 4, 5], 6, [-1, -1])
    check([-3, -2, -2, -2, 0, 4], -2, [1, 3])

    print("all tests passed")

run_tests()

Test meaning: