#34

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find First and Last Position of Element in Sorted Array

Locate the first and last index of a target in a sorted array using binary search for precise O(log n) performance.

Problem Statement

Given a sorted array of integers, determine the first and last positions of a specified target value. Return [-1,-1] if the target does not exist in the array. The array may be empty, and integers can range widely.

Your algorithm must achieve O(log n) time complexity, leveraging the sorted property to avoid linear scans. Carefully consider boundary conditions when the target appears at the start or end, and handle duplicates correctly.

Examples

Example 1

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

Output: [3,4]

Example details omitted.

Example 2

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

Output: [-1,-1]

Example details omitted.

Example 3

Input: nums = [], target = 0

Output: [-1,-1]

Example details omitted.

Constraints

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

Solution Approach

Binary Search for Left Boundary

Perform a standard binary search biased to the left: when nums[mid] >= target, move the high pointer; when nums[mid] < target, move the low pointer. Stop when low meets high to find the first occurrence. This ensures no unnecessary scanning and maintains O(log n) complexity.

Binary Search for Right Boundary

Repeat binary search but biased to the right: when nums[mid] <= target, move the low pointer; when nums[mid] > target, move the high pointer. This identifies the last occurrence. Ensuring correct adjustment of mid and pointers avoids overshooting and captures duplicates correctly.

Combine Results and Validate

After locating potential boundaries, check if the target actually exists at the computed indices. If not found, return [-1,-1]. This final step prevents false positives from empty arrays or targets outside the array range.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) because each boundary search halves the search space. Space complexity is O(1) since no extra structures are used; only pointers and indices are maintained.

What Interviewers Usually Probe

Check if the candidate identifies both leftmost and rightmost positions using separate searches.
Listen for correct pointer movement logic to handle duplicates without scanning the entire array.
Expect clarification on edge cases, such as empty arrays or targets at array boundaries.

Common Pitfalls or Variants

Common pitfalls

Using a single binary search and assuming the first match is the left boundary.
Incorrect pointer updates that skip valid duplicates, causing wrong last position.
Neglecting validation after search, which can return indices when target is absent.

Follow-up variants

Find the count of target occurrences using the same binary search boundaries approach.
Return all ranges of multiple target values efficiently in one pass.
Handle rotated sorted arrays while still identifying first and last positions with modified binary search.

FAQ

What is the best strategy to find the first and last positions of a target in a sorted array?

Use two separate binary searches, one biased left for the first occurrence and one biased right for the last occurrence, ensuring O(log n) efficiency.

How do I handle cases where the target is not present?

After computing the left and right boundaries, validate that nums[left] and nums[right] match the target; otherwise return [-1,-1].

Can this approach work for arrays with duplicates?

Yes, separate left-biased and right-biased binary searches correctly identify the extreme indices even when multiple duplicates exist.

What if the array is empty?

Immediately return [-1,-1] since the binary search will find no valid indices, preventing errors.

Does this problem pattern always require O(log n) solutions?

Yes, the pattern 'binary search over the valid answer space' ensures logarithmic performance, which is necessary for interview expectations.

terminal

Solution

Solution 1: Binary Search

We can perform two binary searches to find the left boundary and the right boundary.

1

2

3

4

5

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = bisect_left(nums, target)
        r = bisect_left(nums, target + 1)
        return [-1, -1] if l == r else [l, r - 1]

Continue Practicing

#33 search in rotated sorted array #35 search insert position #4 median of two sorted arrays