34. Find First And Last Position of Element In Sorted Array - Explanation

Description

You are given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Output: [3,4]

Example 2:

Input: nums = [1], target = 1

Output: [0,0]

Constraints:

0 <= nums.length <= 100,000
-1,000,000,000 <= nums[i], target <= 1,000,000,000
nums is a non-decreasing array.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

Since the array is sorted, all occurrences of the target will be consecutive. We can scan through the array once, recording the first and last positions where we encounter the target. The first time we see the target, we set both the start and end to that index. For subsequent matches, we only update the end position.

Algorithm

Initialize result array res = [-1, -1].
Iterate through the array with index i:
- If nums[i] equals the target:
  - If res[0] is still -1, set both res[0] and res[1] to i.
  - Otherwise, update res[1] to i.
Return res.

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res = [-1, -1]

        for i, num in enumerate(nums):
            if num == target:
                if res[0] == -1:
                    res[0] = res[1] = i
                else:
                    res[1] = i

        return res

Time & Space Complexity

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

2. Binary Search - I

Intuition

Binary search can find any occurrence of the target in O(log n) time, but we need both the first and last occurrences. The key insight is that when we find the target, instead of returning immediately, we continue searching. For the leftmost occurrence, we search the left half after finding a match. For the rightmost, we search the right half. This gives us two separate binary searches with a bias parameter.

Algorithm

Implement a binary search helper that takes a leftBias parameter.
When nums[m] == target:
- Record index m as a candidate.
- If leftBias is true, continue searching left (r = m - 1).
- Otherwise, continue searching right (l = m + 1).
Call the helper twice: once with leftBias = true for the start position, and once with leftBias = false for the end position.
Return [left, right].

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.binarySearch(nums, target, True)
        right = self.binarySearch(nums, target, False)
        return [left, right]

    def binarySearch(self, nums, target, leftBias):
        l, r = 0, len(nums) - 1
        i = -1
        while l <= r:
            m = (l + r) // 2
            if target > nums[m]:
                l = m + 1
            elif target < nums[m]:
                r = m - 1
            else:
                i = m
                if leftBias:
                    r = m - 1
                else:
                    l = m + 1
        return i

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Binary Search - II

Intuition

We can use a single style of binary search that finds the insertion point for a value. The insertion point for target gives us the first occurrence (if it exists). The insertion point for target + 1 gives us one past the last occurrence. This approach uses the standard lower-bound binary search pattern, which finds the smallest index where nums[index] >= target.

Algorithm

Implement a binary search that finds the leftmost position where nums[m] >= target.
Find start = binarySearch(target).
If start equals the array length or nums[start] != target, return [-1, -1].
Find end = binarySearch(target + 1) - 1.
Return [start, end].

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        def binarySearch(target):
            l, r = 0, n
            while l < r:
                m = l + (r - l) // 2
                if nums[m] >= target:
                    r = m
                else:
                    l = m + 1
            return l

        start = binarySearch(target)
        if start == n or nums[start] != target:
            return [-1, -1]

        return [start, binarySearch(target + 1) - 1]

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. In-Built Function

Intuition

Most programming languages provide built-in functions for binary search that find lower and upper bounds. These functions are optimized and well-tested, making them a practical choice when available. The lower bound gives the first occurrence, and the upper bound (minus one) gives the last occurrence.

Algorithm

Use the language's built-in lower-bound function to find the first position where the target could be inserted.
If this position is out of bounds or doesn't contain the target, return [-1, -1].
Use the upper-bound function to find the position just after the last occurrence.
Return [lower_bound, upper_bound - 1].

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect.bisect_left(nums, target)
        if left >= len(nums) or nums[left] != target:
            return [-1, -1]

        right = bisect.bisect_right(nums, target) - 1
        return [left, right]

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Returning Early When Target Is Found

Standard binary search returns immediately upon finding the target, but this gives an arbitrary occurrence, not the first or last. You must continue searching (leftward for first, rightward for last) even after finding a match to locate the boundary positions.

Not Handling the Target-Not-Found Case

After performing binary search for the first occurrence, you must verify that the found index actually contains the target. If the target does not exist in the array, the binary search returns an insertion point, not a valid position. Always check bounds and value equality before returning.

Off-by-One Errors in Boundary Calculation

When using lower-bound and upper-bound style searches, the upper bound points to one past the last occurrence. Forgetting to subtract 1 when computing the end position, or using incorrect loop conditions (l <= r vs l < r), leads to wrong indices or infinite loops.