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

MediumArrayBinary Search

LeetCode ↗

Problem Idea Example Code Visual Complex Pitfalls

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].

Pattern Learn more about Binary Search patterns.

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

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]

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 findFirstTrue(findGreater: bool) -> int:
10            left, right = 0, n - 1
11            firstTrueIndex = -1
12
13            while left <= right:
14                mid = (left + right) // 2
15                if findGreater:
16                    feasible = nums[mid] > target
17                else:
18                    feasible = nums[mid] >= target
19
20                if feasible:
21                    firstTrueIndex = mid
22                    right = mid - 1
23                else:
24                    left = mid + 1
25
26            return firstTrueIndex
27
28        firstIdx = findFirstTrue(False)
29        if firstIdx == -1 or nums[firstIdx] != target:
30            return [-1, -1]
31
32        afterLastIdx = findFirstTrue(True)
33        if afterLastIdx == -1:
34            lastIdx = n - 1
35        else:
36            lastIdx = afterLastIdx - 1
37
38        return [firstIdx, lastIdx]
39

1class Solution {
2    private int[] nums;
3    private int n;
4
5    public int[] searchRange(int[] nums, int target) {
6        this.nums = nums;
7        this.n = nums.length;
8
9        if (n == 0) {
10            return new int[] {-1, -1};
11        }
12
13        int firstIdx = findFirstTrue(target, false);
14        if (firstIdx == -1 || nums[firstIdx] != target) {
15            return new int[] {-1, -1};
16        }
17
18        int afterLastIdx = findFirstTrue(target, true);
19        int lastIdx;
20        if (afterLastIdx == -1) {
21            lastIdx = n - 1;
22        } else {
23            lastIdx = afterLastIdx - 1;
24        }
25
26        return new int[] {firstIdx, lastIdx};
27    }
28
29    private int findFirstTrue(int target, boolean findGreater) {
30        int left = 0;
31        int right = n - 1;
32        int firstTrueIndex = -1;
33
34        while (left <= right) {
35            int mid = left + (right - left) / 2;
36            boolean feasible;
37            if (findGreater) {
38                feasible = nums[mid] > target;
39            } else {
40                feasible = nums[mid] >= target;
41            }
42
43            if (feasible) {
44                firstTrueIndex = mid;
45                right = mid - 1;
46            } else {
47                left = mid + 1;
48            }
49        }
50
51        return firstTrueIndex;
52    }
53}
54

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        auto findFirstTrue = [&](bool findGreater) -> int {
10            int left = 0;
11            int right = n - 1;
12            int firstTrueIndex = -1;
13
14            while (left <= right) {
15                int mid = left + (right - left) / 2;
16                bool feasible;
17                if (findGreater) {
18                    feasible = nums[mid] > target;
19                } else {
20                    feasible = nums[mid] >= target;
21                }
22
23                if (feasible) {
24                    firstTrueIndex = mid;
25                    right = mid - 1;
26                } else {
27                    left = mid + 1;
28                }
29            }
30
31            return firstTrueIndex;
32        };
33
34        int firstIdx = findFirstTrue(false);
35        if (firstIdx == -1 || nums[firstIdx] != target) {
36            return {-1, -1};
37        }
38
39        int afterLastIdx = findFirstTrue(true);
40        int lastIdx;
41        if (afterLastIdx == -1) {
42            lastIdx = n - 1;
43        } else {
44            lastIdx = afterLastIdx - 1;
45        }
46
47        return {firstIdx, lastIdx};
48    }
49};
50

1function searchRange(nums: number[], target: number): number[] {
2    const n: number = nums.length;
3
4    if (n === 0) {
5        return [-1, -1];
6    }
7
8    const findFirstTrue = (findGreater: boolean): number => {
9        let left: number = 0;
10        let right: number = n - 1;
11        let firstTrueIndex: number = -1;
12
13        while (left <= right) {
14            const mid: number = Math.floor((left + right) / 2);
15            let feasible: boolean;
16            if (findGreater) {
17                feasible = nums[mid] > target;
18            } else {
19                feasible = nums[mid] >= target;
20            }
21
22            if (feasible) {
23                firstTrueIndex = mid;
24                right = mid - 1;
25            } else {
26                left = mid + 1;
27            }
28        }
29
30        return firstTrueIndex;
31    };
32
33    const firstIdx: number = findFirstTrue(false);
34    if (firstIdx === -1 || nums[firstIdx] !== target) {
35        return [-1, -1];
36    }
37
38    const afterLastIdx: number = findFirstTrue(true);
39    let lastIdx: number;
40    if (afterLastIdx === -1) {
41        lastIdx = n - 1;
42    } else {
43        lastIdx = afterLastIdx - 1;
44    }
45
46    return [firstIdx, lastIdx];
47}
48

Visualization

AlgoMonster exclusive: step through the algorithm state, not just the final code.

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.

Pattern 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

Ready to land your dream job?

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

Start Evaluator

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

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know