LeetCode · #34

Find First and Last Position of Element in Sorted Array Solution

Given a sorted array with possible duplicates, return the first and last index of a target. If the target does not exist, return [-1, -1].

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #34

🏗️

Pattern

Binary Search — lower/upper bounds

The array is sorted, so duplicates form one contiguous block. If we can find the left boundary of that block and the first index strictly after it, we can recover the full answer in O(log n).

Example

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

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

Section Two · Approach 1

Linear Scan — O(n)

Scan from left to right, remember the first time you see the target, and keep updating the last time you see it.

Problem: This ignores the sorted property. The whole point of the problem is to use binary search to find the duplicate boundaries directly in O(log n).

Section Three · Approach 2

Lower Bound + Upper Bound — O(log n)

Run two boundary searches:

lowerBound(target): first index i such that nums[i] >= target
upperBound(target): first index i such that nums[i] > target

If lowerBound points outside the array or to a different value, the target is absent. Otherwise the answer is:

[lowerBound(target), upperBound(target) - 1]

💡 Mental model: Imagine a sorted row of books where all copies of the same title sit together. Lower bound finds where the target title starts. Upper bound finds the first shelf slot after that title ends.

Recognition signal: Whenever a binary-search problem says “first occurrence,” “last occurrence,” “range of duplicates,” or “insertion point,” think in terms of lower and upper bounds, not exact-match binary search.

Section Four · Trace

Visual Walkthrough

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

LC 34 — boundary finding with two binary searches

Section Five · Implementation

Code — Java & Python

Java — lower bound and upper bound

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = lowerBound(nums, target);
        if (first == nums.length || nums[first] != target) return new int[] { -1, -1 };
        int last = upperBound(nums, target) - 1;
        return new int[] { first, last };
    }

    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }

    private int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

Python — two boundary searches

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def lower_bound() -> int:
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            return left

        def upper_bound() -> int:
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid
            return left

        first = lower_bound()
        if first == len(nums) or nums[first] != target:
            return [-1, -1]
        return [first, upper_bound() - 1]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Linear scan	O(n)	O(1)	Simple but ignores sorted order.
Bounds-based binary search ← optimal	O(log n)	O(1)	Finds both duplicate boundaries directly.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Target missing	Return `[-1,-1]`	Always validate lower bound before using it.
All values equal target	Return full array range	Bounds should expand to both ends correctly.
Single occurrence	First and last are the same index	Upper bound still returns one past that index.
Empty array	Return `[-1,-1]`	The lower bound will be 0, equal to array length.
Using exact-match binary search	Unreliable for duplicates	It can land on any duplicate, not necessarily the first or last.

⚠ Common Mistake: Returning [lowerBound, upperBound] instead of [lowerBound, upperBound - 1]. Upper bound points to the first index after the target block, so subtract 1 for the last actual occurrence.

← Back to Binary Search problems

LearningTree

LC 34 · Find First and Last Position of Element in Sorted Array — Solution & Explanation | DSA Guide