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

LeetCode Problem 34

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us a sorted integer array nums and a target value target. Our goal is to find the first position where the target appears and the last position where the target appears.

The array is sorted in non-decreasing order, which means duplicate values appear next to each other. Because of this ordering property, we can use binary search techniques instead of scanning the array linearly.

The output should be a two-element array:

• The first value is the index of the first occurrence of target
• The second value is the index of the last occurrence of target

If the target does not exist in the array, we return [-1, -1].

For example:

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

The target 8 appears twice, at indices 3 and 4, so the answer is:

[3,4]

The key requirement is the runtime complexity. The problem explicitly requires an O(log n) algorithm. This requirement immediately rules out any straightforward linear scan solution because scanning the entire array takes O(n) time.

The constraints tell us several important things:

• The array length can be as large as 10^5
• Values may be negative or positive
• The array is already sorted
• Duplicate values are allowed

The sorted property is the most important observation because binary search only works efficiently on ordered data.

Several edge cases are important:

• The array may be empty
• The target may not exist
• Every element may equal the target
• The target may appear only once
• The target may appear at the beginning or end of the array

A naive implementation can easily make off-by-one mistakes when searching for boundaries, especially when duplicates exist.

Approaches

Brute Force Approach

The most straightforward solution is to scan the array from left to right.

We could initialize two variables, first and last, to -1. As we iterate through the array:

• When we encounter the target for the first time, we set first
• Every time we encounter the target, we update last

At the end of the traversal, first and last contain the desired range.

This approach is correct because it checks every element and records all occurrences of the target. However, it takes O(n) time because in the worst case we may need to scan the entire array.

Since the problem explicitly requires O(log n) complexity, this solution is too slow.

Optimal Binary Search Approach

The important insight is that the array is sorted.

In a sorted array, binary search can efficiently locate values in logarithmic time. However, a standard binary search only finds one occurrence of the target, not necessarily the first or last.

To solve this problem efficiently, we perform two separate binary searches:

• One search finds the leftmost occurrence of the target
• Another search finds the rightmost occurrence of the target

The idea is to continue searching even after finding the target:

• For the first occurrence, we move left whenever we find the target
• For the last occurrence, we move right whenever we find the target

This works because duplicates are contiguous in a sorted array.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scans entire array and tracks first and last occurrence
Optimal	O(log n)	O(1)	Uses two binary searches to find left and right boundaries

Algorithm Walkthrough

Step 1: Search for the First Occurrence

We perform a binary search to locate the leftmost position of the target.

When nums[mid] equals the target:

• We record mid as a possible answer
• We continue searching the left half because there may be another occurrence earlier in the array

When nums[mid] is smaller than the target:

• The target must be to the right
• Move left forward

When nums[mid] is larger than the target:

• The target must be to the left
• Move right backward

At the end of this search, we either have the first occurrence index or -1.

Step 2: Search for the Last Occurrence

We repeat binary search with slightly different behavior.

When nums[mid] equals the target:

• We record mid
• We continue searching the right half because there may be another occurrence later in the array

The remaining comparisons are identical to standard binary search.

At the end of this search, we either have the last occurrence index or -1.

Step 3: Return the Result

Combine the results from both searches into a two-element array:

[first_occurrence, last_occurrence]

If the target was never found, both values remain -1.

Why it works

The correctness comes from the binary search invariant.

During the first search, whenever we find the target, we do not stop immediately because there may still be an earlier occurrence. By continuing into the left half, we guarantee that the final recorded index is the smallest valid index containing the target.

Similarly, during the second search, continuing into the right half guarantees that the final recorded index is the largest valid index containing the target.

Because each binary search halves the search space at every step, the runtime remains logarithmic.

Python Solution

from typing import List

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

        def find_first() -> int:
            left, right = 0, len(nums) - 1
            answer = -1

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

                if nums[mid] == target:
                    answer = mid
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return answer

        def find_last() -> int:
            left, right = 0, len(nums) - 1
            answer = -1

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

                if nums[mid] == target:
                    answer = mid
                    left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return answer

        first = find_first()

        if first == -1:
            return [-1, -1]

        last = find_last()

        return [first, last]

The implementation defines two helper functions.

The find_first function performs binary search while biasing toward the left side. Whenever the target is found, the current index is stored in answer, but the search continues in the left half by moving right = mid - 1.

The find_last function is almost identical, except it biases toward the right side. After finding the target, it moves left = mid + 1 to continue searching for later occurrences.

The main function first searches for the first occurrence. If the target does not exist, it immediately returns [-1, -1]. Otherwise, it performs the second search and returns both indices.

This structure keeps the code clean and makes the two boundary searches easy to understand independently.

Go Solution

func searchRange(nums []int, target int) []int {

	findFirst := func() int {
		left, right := 0, len(nums)-1
		answer := -1

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

			if nums[mid] == target {
				answer = mid
				right = mid - 1
			} else if nums[mid] < target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}

		return answer
	}

	findLast := func() int {
		left, right := 0, len(nums)-1
		answer := -1

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

			if nums[mid] == target {
				answer = mid
				left = mid + 1
			} else if nums[mid] < target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}

		return answer
	}

	first := findFirst()

	if first == -1 {
		return []int{-1, -1}
	}

	last := findLast()

	return []int{first, last}
}

The Go implementation follows the same logic as the Python version.

One important Go-specific detail is the midpoint calculation:

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

This form avoids potential integer overflow that can occur with (left + right) / 2 in some languages.

Go slices naturally handle empty arrays, so no special nil handling is required. If the slice is empty, right becomes -1, causing the binary search loop to terminate immediately.

Worked Examples

Example 1

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

Finding First Occurrence

left	right	mid	nums[mid]	action
0	5	2	7	move left pointer right
3	5	4	8	record 4, search left half
3	3	3	8	record 3, search left half

Result:

first = 3

Finding Last Occurrence

left	right	mid	nums[mid]	action
0	5	2	7	move left pointer right
3	5	4	8	record 4, search right half
5	5	5	10	move right pointer left

Result:

last = 4

Final answer:

[3,4]

Example 2

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

Finding First Occurrence

left	right	mid	nums[mid]	action
0	5	2	7	move right pointer left
0	1	0	5	move left pointer right
1	1	1	7	move right pointer left

The target is never found.

Result:

[-1,-1]

Example 3

nums = []
target = 0

Initial values:

left = 0
right = -1

The loop condition left <= right is immediately false, so the function returns:

[-1,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Two binary searches, each taking logarithmic time
Space	O(1)	Only constant extra variables are used

Each binary search cuts the search space in half at every iteration, which gives logarithmic complexity. Since we perform two independent binary searches, the total runtime is still O(log n) because constant factors are ignored in asymptotic analysis.

The algorithm uses only a few integer variables and does not allocate additional data structures proportional to input size, so the space complexity is constant.

Test Cases

from typing import List

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

        def find_first() -> int:
            left, right = 0, len(nums) - 1
            answer = -1

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

                if nums[mid] == target:
                    answer = mid
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return answer

        def find_last() -> int:
            left, right = 0, len(nums) - 1
            answer = -1

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

                if nums[mid] == target:
                    answer = mid
                    left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return answer

        first = find_first()

        if first == -1:
            return [-1, -1]

        last = find_last()

        return [first, last]

solution = Solution()

assert solution.searchRange([5,7,7,8,8,10], 8) == [3,4]  # target appears multiple times
assert solution.searchRange([5,7,7,8,8,10], 6) == [-1,-1]  # target absent
assert solution.searchRange([], 0) == [-1,-1]  # empty array
assert solution.searchRange([1], 1) == [0,0]  # single element present
assert solution.searchRange([1], 2) == [-1,-1]  # single element absent
assert solution.searchRange([2,2,2,2], 2) == [0,3]  # all elements equal target
assert solution.searchRange([1,2,3,4,5], 1) == [0,0]  # target at beginning
assert solution.searchRange([1,2,3,4,5], 5) == [4,4]  # target at end
assert solution.searchRange([1,2,2,2,3], 2) == [1,3]  # target in middle
assert solution.searchRange([1,1,2,3,3,3,4], 3) == [3,5]  # multiple duplicates

Test	Why
[5,7,7,8,8,10], 8	Standard duplicate target case
[5,7,7,8,8,10], 6	Target does not exist
[], 0	Empty array handling
[1], 1	Single-element success case
[1], 2	Single-element failure case
[2,2,2,2], 2	Entire array matches target
[1,2,3,4,5], 1	Target at beginning
[1,2,3,4,5], 5	Target at end
[1,2,2,2,3], 2	Target spans middle section
[1,1,2,3,3,3,4], 3	Multiple repeated elements

Edge Cases

Empty Array

An empty array is one of the most important edge cases because binary search implementations can easily fail with invalid indices.

For an empty array:

nums = []

The initial values become:

left = 0
right = -1

Since left <= right is immediately false, the loop never executes. The implementation correctly returns [-1, -1] without accessing invalid indices.

All Elements Equal the Target

Consider:

nums = [2,2,2,2]
target = 2

A careless binary search might stop at the first discovered occurrence and incorrectly return only a middle index.

Our implementation avoids this by continuing the search even after finding the target:

• The first-occurrence search keeps moving left
• The last-occurrence search keeps moving right

This guarantees the full range [0,3].

Target at the Boundary

Targets at the beginning or end of the array frequently expose off-by-one errors.

Example:

nums = [1,2,3,4,5]
target = 1

During the first-occurrence search, the algorithm continues shrinking toward the leftmost valid position until no smaller valid index exists.

Similarly, for:

target = 5

The last-occurrence search continues toward the right boundary.

Because the loop conditions and pointer updates are carefully designed, the implementation correctly handles both extremes without skipping valid indices.