34. Find First and Last Position of Element in Sorted Array

Problem Description

You are given an array of integers nums that is sorted in non-decreasing order (ascending order, allowing duplicates). Your task is to find the starting and ending positions of a given target value within this array.

The function should return an array of two integers [start, end] where:

start is the index of the first occurrence of target in the array
end is the index of the last occurrence of target in the array

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

The key constraint is that your algorithm must achieve O(log n) runtime complexity, which means you need to use a binary search approach rather than a linear scan.

For example:

If nums = [5,7,7,8,8,10] and target = 8, the output should be [3,4] because 8 appears at indices 3 and 4
If nums = [5,7,7,8,8,10] and target = 6, the output should be [-1,-1] because 6 is not in the array
If nums = [1] and target = 1, the output should be [0,0] because the single element at index 0 matches the target

The solution uses Python's bisect_left function twice:

First to find the leftmost position where target could be inserted (which gives us the starting position if target exists)
Second to find the leftmost position where target + 1 could be inserted (which gives us one position after the last occurrence of target)

If these two positions are the same (l == r), it means target doesn't exist in the array, so we return [-1, -1]. Otherwise, we return [l, r-1] as the range.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Since the array is sorted and we need O(log n) complexity, binary search is the natural choice. We need to find both the first and last occurrences of the target, which means running binary search twice with different feasible conditions.

Finding the First Occurrence: We want the first index where nums[i] >= target. This is a classic boundary-finding problem:

Pattern: false, false, ..., false, true, true, ..., true
Feasible condition: nums[mid] >= target
We're looking for the first true in this pattern

Finding the Last Occurrence: We want the last index where nums[i] <= target. We can transform this to find the first index where nums[i] > target, then subtract 1:

Pattern: false, false, ..., false, true, true, ..., true
Feasible condition: nums[mid] > target
The last occurrence is at first_true_index - 1

Alternatively, we can search for the first position where target + 1 would be inserted, which gives us the same result.

For example, with [5,7,7,8,8,8,10] and target = 8:

First binary search finds index 3 (first 8)
Second binary search finds index 6 (first position > 8), so last 8 is at index 5
Result: [3, 5]

If the target doesn't exist, the first search will return an index where nums[index] != target, and we return [-1, -1].

Learn more about Binary Search patterns.

Solution Implementation

1from typing import List
2
3class Solution:
4    def searchRange(self, nums: List[int], target: int) -> List[int]:
5        n = len(nums)
6        if n == 0:
7            return [-1, -1]
8
9        def find_first_true(feasible):
10            """Binary search template to find first index where feasible(mid) is True."""
11            left, right = 0, n - 1
12            first_true_index = -1
13
14            while left <= right:
15                mid = (left + right) // 2
16                if feasible(mid):
17                    first_true_index = mid
18                    right = mid - 1
19                else:
20                    left = mid + 1
21
22            return first_true_index
23
24        # Find first occurrence: first index where nums[i] >= target
25        first_idx = find_first_true(lambda mid: nums[mid] >= target)
26
27        # Check if target exists at first_idx
28        if first_idx == -1 or nums[first_idx] != target:
29            return [-1, -1]
30
31        # Find last occurrence: first index where nums[i] > target, then subtract 1
32        after_last_idx = find_first_true(lambda mid: nums[mid] > target)
33
34        # If no element > target exists, last occurrence is at the end
35        if after_last_idx == -1:
36            last_idx = n - 1
37        else:
38            last_idx = after_last_idx - 1
39
40        return [first_idx, last_idx]
41

1class Solution {
2    private int[] nums;
3    private int n;
4
5    /**
6     * Find the starting and ending position of a given target value in a sorted array.
7     * Uses the binary search template with first_true_index tracking.
8     */
9    public int[] searchRange(int[] nums, int target) {
10        this.nums = nums;
11        this.n = nums.length;
12
13        if (n == 0) {
14            return new int[] {-1, -1};
15        }
16
17        // Find first occurrence: first index where nums[i] >= target
18        int firstIdx = findFirstTrue(target, true);
19
20        // Check if target exists at firstIdx
21        if (firstIdx == -1 || nums[firstIdx] != target) {
22            return new int[] {-1, -1};
23        }
24
25        // Find last occurrence: first index where nums[i] > target, then subtract 1
26        int afterLastIdx = findFirstTrue(target, false);
27
28        int lastIdx;
29        if (afterLastIdx == -1) {
30            // No element > target exists, last occurrence is at the end
31            lastIdx = n - 1;
32        } else {
33            lastIdx = afterLastIdx - 1;
34        }
35
36        return new int[] {firstIdx, lastIdx};
37    }
38
39    /**
40     * Binary search template to find first index where condition is true.
41     * @param target - the target value
42     * @param findGreaterOrEqual - if true, finds first nums[i] >= target; if false, finds first nums[i] > target
43     */
44    private int findFirstTrue(int target, boolean findGreaterOrEqual) {
45        int left = 0;
46        int right = n - 1;
47        int firstTrueIndex = -1;
48
49        while (left <= right) {
50            int mid = left + (right - left) / 2;
51
52            boolean feasible = findGreaterOrEqual ? nums[mid] >= target : nums[mid] > target;
53
54            if (feasible) {
55                firstTrueIndex = mid;
56                right = mid - 1;
57            } else {
58                left = mid + 1;
59            }
60        }
61
62        return firstTrueIndex;
63    }
64}
65

1class Solution {
2public:
3    vector<int> searchRange(vector<int>& nums, int target) {
4        int n = nums.size();
5        if (n == 0) {
6            return {-1, -1};
7        }
8
9        // Binary search template to find first index where condition is true
10        auto findFirstTrue = [&](bool findGreaterOrEqual) -> int {
11            int left = 0;
12            int right = n - 1;
13            int firstTrueIndex = -1;
14
15            while (left <= right) {
16                int mid = left + (right - left) / 2;
17
18                bool feasible = findGreaterOrEqual ? nums[mid] >= target : nums[mid] > target;
19
20                if (feasible) {
21                    firstTrueIndex = mid;
22                    right = mid - 1;
23                } else {
24                    left = mid + 1;
25                }
26            }
27
28            return firstTrueIndex;
29        };
30
31        // Find first occurrence: first index where nums[i] >= target
32        int firstIdx = findFirstTrue(true);
33
34        // Check if target exists at firstIdx
35        if (firstIdx == -1 || nums[firstIdx] != target) {
36            return {-1, -1};
37        }
38
39        // Find last occurrence: first index where nums[i] > target, then subtract 1
40        int afterLastIdx = findFirstTrue(false);
41
42        int lastIdx;
43        if (afterLastIdx == -1) {
44            // No element > target exists, last occurrence is at the end
45            lastIdx = n - 1;
46        } else {
47            lastIdx = afterLastIdx - 1;
48        }
49
50        return {firstIdx, lastIdx};
51    }
52};
53

1/**
2 * Finds the first and last position of a target value in a sorted array.
3 * Uses the binary search template with first_true_index tracking.
4 */
5function searchRange(nums: number[], target: number): number[] {
6    const n: number = nums.length;
7
8    if (n === 0) {
9        return [-1, -1];
10    }
11
12    /**
13     * Binary search template to find first index where condition is true.
14     */
15    const findFirstTrue = (findGreaterOrEqual: boolean): number => {
16        let left: number = 0;
17        let right: number = n - 1;
18        let firstTrueIndex: number = -1;
19
20        while (left <= right) {
21            const mid: number = Math.floor((left + right) / 2);
22
23            const feasible: boolean = findGreaterOrEqual
24                ? nums[mid] >= target
25                : nums[mid] > target;
26
27            if (feasible) {
28                firstTrueIndex = mid;
29                right = mid - 1;
30            } else {
31                left = mid + 1;
32            }
33        }
34
35        return firstTrueIndex;
36    };
37
38    // Find first occurrence: first index where nums[i] >= target
39    const firstIdx: number = findFirstTrue(true);
40
41    // Check if target exists at firstIdx
42    if (firstIdx === -1 || nums[firstIdx] !== target) {
43        return [-1, -1];
44    }
45
46    // Find last occurrence: first index where nums[i] > target, then subtract 1
47    const afterLastIdx: number = findFirstTrue(false);
48
49    let lastIdx: number;
50    if (afterLastIdx === -1) {
51        // No element > target exists, last occurrence is at the end
52        lastIdx = n - 1;
53    } else {
54        lastIdx = afterLastIdx - 1;
55    }
56
57    return [firstIdx, lastIdx];
58}
59

Solution Approach

We use the standard binary search template twice to find both boundaries. Each search uses first_true_index = -1 to track the answer.

Template Structure:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

Step 1: Find the first occurrence

Feasible condition: nums[mid] >= target
This finds the first index where nums[i] >= target
If found, verify that nums[first_true_index] == target

Step 2: Find the last occurrence

Feasible condition: nums[mid] > target
This finds the first index where nums[i] > target
The last occurrence of target is at first_true_index - 1
If first_true_index == -1, all elements are <= target, so check the last element

Alternative for Step 2: Search for target + 1:

Feasible condition: nums[mid] >= target + 1
This finds the insertion point for target + 1
The last occurrence of target is at first_true_index - 1

Time Complexity: O(log n) - Two binary searches, each taking O(log n) time

Space Complexity: O(1) - Only using a constant amount of extra space for variables

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a detailed example with nums = [2,2,3,4,4,4,5] and target = 4:

Step 1: Find the first occurrence of 4

Using the template with feasible condition nums[mid] >= 4:

Initial: left = 0, right = 6, first_true_index = -1
Iteration 1: mid = 3, nums[3] = 4 >= 4 → first_true_index = 3, right = 2
Iteration 2: mid = 1, nums[1] = 2 >= 4? No → left = 2
Iteration 3: mid = 2, nums[2] = 3 >= 4? No → left = 3
Loop ends (left > right)
Result: first_true_index = 3, verify nums[3] = 4 == target ✓

First occurrence is at index 3.

Step 2: Find the last occurrence of 4

Using the template with feasible condition nums[mid] > 4:

Initial: left = 0, right = 6, first_true_index = -1
Iteration 1: mid = 3, nums[3] = 4 > 4? No → left = 4
Iteration 2: mid = 5, nums[5] = 4 > 4? No → left = 6
Iteration 3: mid = 6, nums[6] = 5 > 4? Yes → first_true_index = 6, right = 5
Loop ends (left > right)
Result: first_true_index = 6, last occurrence is at 6 - 1 = 5

Last occurrence is at index 5.

Final Result: [3, 5]

Verification: In [2,2,3,4,4,4,5], the value 4 appears at indices 3, 4, and 5, so [3,5] is correct!

Edge Case Example:

For the same array with target = 1 (not in array):

First search: first_true_index = 0 (first element >= 1), but nums[0] = 2 != 1
Since target not found, return [-1, -1]

Time and Space Complexity

Time Complexity: O(log n), where n is the length of the array nums. The algorithm uses two binary search operations with the template (while left <= right). Each search takes O(log n) time since the search space is halved in each iteration. Total: O(log n) + O(log n) = O(log n).

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for variables (left, right, mid, firstTrueIndex), regardless of the input size. No recursive calls or additional data structures are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: Using while left < right with right = mid instead of the standard template with first_true_index tracking.

Example of the Issue:

# Non-standard variant
while left < right:
    mid = (left + right) // 2
    if nums[mid] >= target:
        right = mid
    else:
        left = mid + 1
return left

Solution: Use the standard binary search template with explicit answer tracking:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if nums[mid] >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

2. Not Verifying Target Exists After First Search

The Pitfall: Assuming the first search result is valid without checking if nums[first_true_index] == target.

Example Scenario:

nums = [1, 3, 5, 7]
target = 4
# First search returns 2 (first element >= 4), but nums[2] = 5 != 4

Solution: Always verify that the target actually exists at the found position:

first_idx = find_first_true(lambda mid: nums[mid] >= target)

if first_idx == -1 or nums[first_idx] != target:
    return [-1, -1]

3. Handling Empty Arrays Incorrectly

The Pitfall: Not checking for empty arrays before performing binary search, which can cause index errors.

Solution: Add an explicit check for empty arrays:

if n == 0:
    return [-1, -1]

4. Incorrect Logic for Finding Last Occurrence

The Pitfall: Trying to find the last occurrence directly instead of finding "first element > target" and subtracting 1.

Solution: Use the pattern: find first index where nums[mid] > target, then subtract 1:

# Find first index where nums[i] > target
after_last_idx = find_first_true(lambda mid: nums[mid] > target)

# Handle case where no element > target exists
if after_last_idx == -1:
    last_idx = n - 1  # Last occurrence is at the end
else:
    last_idx = after_last_idx - 1

5. Edge Case: All Elements Equal to Target

The Pitfall: When all elements equal the target, the second search returns -1 (no element > target).

Solution: Handle the case where after_last_idx == -1:

if after_last_idx == -1:
    last_idx = n - 1  # Last element is the last occurrence
else:
    last_idx = after_last_idx - 1

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know