Find First and Last Position of Element in Sorted Array

Difficulty: Medium
Topics: Array, Binary Search
Link: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Problem Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

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

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

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

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement

Given a sorted array nums of integers arranged in non-decreasing order, design an algorithm that returns the starting index i and ending index j of a contiguous subarray where every element equals the target value target. The algorithm must:

Operate in O(log n) time complexity, where n = len(nums)
Return [-1, -1] if target ∉ nums
Handle edge cases including empty arrays and single-element arrays
The solution must leverage the sorted property to achieve logarithmic runtime, not linear scanning

Formally:
Given nums = [a₀, a₁, ..., aₙ₋₁] where aₖ ≤ aₖ₊₁ for 0 ≤ k < n-1,
Find [L, R] such that:

aₖ = target for all k ∈ [L, R]
aₖ ≠ target for all k < L and k > R
If no such k exists, return [-1, -1]

Beginner Restatement

You have a list of numbers that are already sorted from smallest to largest. You’re looking for a specific number in this list. If the number appears multiple times in a row, you need to find where it starts and where it ends. If the number isn’t in the list at all, report that by returning [-1, -1]. You need to do this efficiently without checking every single number one by one.

Mathematical Restatement

Given a monotonically non-decreasing sequence {aᵢ}ᵢ₌₀ⁿ⁻¹ and a scalar t ∈ ℤ, define:

Let S = {i ∈ [0, n-1] : aᵢ = t}

If S = ∅, return (-1, -1)
Otherwise, return (min(S), max(S))

Alternative formulation using indicator functions:
Find L = argminₖ [aₖ = t] and R = argmaxₖ [aₖ = t]
Subject to: 0 ≤ L ≤ R < n and ∀k ∈ [L, R], aₖ = t

Constraint Analysis

0 <= nums.length <= 10⁵

Upper bound of 100,000 elements permits O(n log n) algorithms but demands O(log n) per problem requirement
Lower bound of 0 mandates handling empty arrays as a base case
Memory usage must be efficient; storing multiple copies of the array is prohibitive

-10⁹ <= nums[i] <= 10⁹

Integer values require exact matching; floating-point comparison techniques are irrelevant
Extreme values necessitate 64-bit integers (Python int handles arbitrarily large, but languages like Java/C++ need long)
No overflow concerns during index calculations, but comparisons must handle large magnitudes

nums is a non-decreasing array

Critical property enabling binary search; the sequence may contain duplicates
“Non-decreasing” ≠ “strictly increasing”; consecutive equal elements create plateaus
The target may appear multiple times consecutively, forming a contiguous block

-10⁹ <= target <= 10⁹

Target may be outside array’s value range, enabling early elimination
No restriction that target must be present; absence detection is required
Extreme values don’t affect algorithm design beyond comparison operations

Runtime Complexity: O(log n)

Eliminates linear scan approaches (O(n))
Requires binary search or variant as fundamental primitive
Multiple binary searches (e.g., two) still satisfy O(log n) since 2·log n = O(log n)
Recursion depth must be controlled to avoid O(n) stack usage

2. Intuition Scaffolding

Analogies Using Topic Tags (Binary Search, Array)

1. Real-World Metaphor: Library Catalog System

Imagine searching for all books by a specific author in a physically organized library where books are alphabetically sorted by author’s last name. You:

First find where the author’s section begins by checking the middle shelf, then moving left/right until you locate the first book by that author
Then find where it ends by searching from that starting point to find the last book by that author This mimics two binary searches—one for left boundary, one for right boundary—instead of scanning every shelf linearly.

2. Gaming Analogy: Treasure Hunt with Clues

In an adventure game, you’re told treasure is buried somewhere between mile markers X and Y on a sorted trail. You receive two binary-search clues:

First clue: “Walk to the middle marker, check if treasure is there. If so, search left half for earlier treasure; if not, search right half”
Second clue: Once found, “From that spot, search rightward to find the last treasure” This sequential narrowing avoids checking every mile marker individually.

3. Mathematical Analogy: Root-Finding in Step Functions

Consider the function f(i) = nums[i] - target. This function is non-decreasing (since nums is sorted). The zero region {i : f(i) = 0} forms an interval. Finding boundaries of this interval is equivalent to:

Finding the first index where f(i) ≥ 0 (left boundary)
Finding the first index where f(i) > 0 (right boundary + 1) These are binary searches for the transition points in a monotonic function.

Common Pitfalls Section

Single Binary Search Only
Searching until finding any target occurrence, then linear scanning left/right → O(n) worst-case when the entire array equals target.
Misadjusted Loop Conditions
Using while left < right versus while left ≤ right incorrectly can cause infinite loops or off-by-one errors in boundary detection.
Incorrect Midpoint Calculation
mid = (left + right) // 2 may overflow in languages with fixed integers (not Python). Safer: left + (right - left) // 2.
Symmetric Search Assumption
Trying to use identical binary search for both boundaries fails because left search finds first ≥ target, right search finds first > target (then subtract 1).
Forgetting Empty Array Check
Not handling nums.length == 0 early causes index errors when accessing nums[0].
Early Termination on First Find
Stopping binary search when nums[mid] == target without continuing to narrow bounds misses the true first/last occurrence.
Confusing Index Boundaries
Returning [left, right] without validating nums[left] == target may return incorrect indices when target is absent.

3. Approach Encyclopedia

Approach 1: Linear Scan (Brute Force)

Pseudocode:

function findRange(nums, target):
    start = -1, end = -1
    for i from 0 to len(nums)-1:
        if nums[i] == target:
            if start == -1:
                start = i
            end = i
        else if nums[i] > target:  # Early exit due to sorted property
            break
    return [start, end]

Complexity Proof:

Time: In worst case, scan entire array → T(n) = c·n operations → O(n)
Space: Only store two indices → O(1)

Visualization:

nums: [5, 7, 7, 8, 8, 10], target = 8
       ↑  ↑  ↑  ↑  ↑  ↑
Scan:  i=0: 5≠8
       i=1: 7≠8
       i=2: 7≠8
       i=3: 8=8 → start=3, end=3
       i=4: 8=8 → end=4
       i=5: 10>8 → break
Result: [3,4]

Approach 2: Binary Search for Boundaries (Optimal)

Core Insight: Use two modified binary searches:

Find leftmost target: Binary search for first index where nums[i] ≥ target, then verify equality
Find rightmost target: Binary search for first index where nums[i] > target, then subtract 1

Left Boundary Search Pseudocode:

function findLeft(nums, target):
    left = 0, right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left  # First position where nums[i] ≥ target

Right Boundary Search Pseudocode:

function findRight(nums, target):
    left = 0, right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    return right  # Last position where nums[i] ≤ target

Complexity Proof:

Each binary search halves search space: T(n) = T(n/2) + O(1) → T(n) = O(log n) by Master Theorem
Two searches: 2·O(log n) = O(log n)
Space: Only indices stored → O(1)

Visualization:

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

LEFT SEARCH (find first ≥8):
Step1: l=0, r=5, mid=2 → nums[2]=7 < 8 → l=3
Step2: l=3, r=5, mid=4 → nums[4]=8 ≥ 8 → r=3
Step3: l=3, r=3, mid=3 → nums[3]=8 ≥ 8 → r=2
Step4: l=3 > r=2 → exit, left_boundary=3

RIGHT SEARCH (find first >8):
Step1: l=0, r=5, mid=2 → nums[2]=7 ≤ 8 → l=3
Step2: l=3, r=5, mid=4 → nums[4]=8 ≤ 8 → l=5
Step3: l=5, r=5, mid=5 → nums[5]=10 > 8 → r=4
Step4: l=5 > r=4 → exit, right_boundary=4

Verify: nums[3]=8, nums[4]=8 → valid

4. Code Deep Dive

Optimal Python Solution with Annotations

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        """
        Find first and last position of target in sorted nums.
        Returns [left_index, right_index] or [-1, -1] if not found.
        """
        
        def find_left_boundary():
            """Binary search for first index where nums[i] >= target"""
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2  # Avoid overflow, though Python handles big ints
                
                # Decision logic: if mid value < target, search right half
                if nums[mid] < target:
                    left = mid + 1  # Move left pointer past mid
                else:
                    right = mid - 1  # Move right pointer to narrow left boundary
            return left  # left points to first position where nums[i] >= target
        
        def find_right_boundary():
            """Binary search for last index where nums[i] <= target"""
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                
                # Decision logic: if mid value <= target, search right half
                if nums[mid] <= target:
                    left = mid + 1  # Move left pointer to narrow right boundary
                else:
                    right = mid - 1  # Move right pointer past mid
            return right  # right points to last position where nums[i] <= target
        
        # Edge case: empty array
        if not nums:
            return [-1, -1]
        
        # Perform binary searches
        left_idx = find_left_boundary()
        right_idx = find_right_boundary()
        
        # Validate that target exists within bounds
        # Check: left_idx within array bounds and nums[left_idx] equals target
        if left_idx <= right_idx and left_idx < len(nums) and nums[left_idx] == target:
            return [left_idx, right_idx]
        else:
            return [-1, -1]

Edge Case Handling

Example 1: nums = [5,7,7,8,8,10], target = 8
- find_left_boundary() returns 3, find_right_boundary() returns 4
- Validation: 3 ≤ 4 and nums[3] == 8 → [3,4]
Example 2: nums = [5,7,7,8,8,10], target = 6
- Left search: finds first ≥6 at index 1 (nums[1]=7)
- Right search: finds last ≤6 at index 0 (nums[0]=5)
- Validation fails: 1 > 0 → returns [-1,-1]
Example 3: nums = [], target = 0
- Early return [-1,-1] due to empty array check
All Elements Equal Target: nums = [8,8,8], target = 8
- Left boundary: 0, Right boundary: 2
- Validation: 0 ≤ 2 and nums[0]==8 → [0,2]
Target at Boundaries: nums = [8,9,10], target = 8
- Left boundary: 0, Right boundary: 0
- Validation passes → [0,0]
Target Larger Than All: nums = [1,2,3], target = 5
- Left boundary: 3 (out of bounds), Right boundary: 2
- Validation fails: 3 > 2 → [-1,-1]

5. Complexity War Room

Hardware-Aware Analysis

For n = 100,000 (maximum constraint):

Memory: Array storage = 100,000 × 8 bytes ≈ 0.8 MB (fits in L2/L3 cache)
Binary Search Iterations: ceil(log₂(100,000)) ≈ 17 iterations per search
Total Operations: ~34 comparisons + arithmetic → negligible CPU time (< 1µs)
Cache Efficiency: Binary search has poor cache locality (random access), but small n makes this negligible
Branch Prediction: Well-predictable comparison patterns (monotonic access)

Comparison with Linear Scan:

Linear: 100,000 comparisons + branch misses
Binary: 34 comparisons + better branch prediction
At scale, binary search is ~3,000× fewer operations

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability	Production Viability
Linear Scan	O(n)	O(1)	10/10 (trivial)	❌ Fails O(log n) requirement	✅ Okay for small n
Built-in Functions*	O(log n) to O(n)	O(1)	9/10	⚠️ Depends on implementation	⚠️ Language-dependent
Two Binary Searches	O(log n)	O(1)	7/10	✅ Optimal for interviews	✅ Recommended
Recursive Binary Search	O(log n)	O(log n) stack	6/10	❌ Space not O(1)	❌ Stack overflow risk
One-Pass Binary + Linear	O(n) worst-case	O(1)	8/10	❌ Worst-case linear	❌ Unacceptable

*Built-in functions: Python’s bisect_left() and bisect_right() provide O(log n) but interviewers often want manual implementation.

6. Pro Mode Extras

Variants Section

Count Occurrences
Once [L,R] found, count = R-L+1. Achieves O(log n) count in sorted array.
First Bad Version (LC 278)
Simplified case: find first occurrence where isBadVersion(i) is True. Use left-boundary search only.
Search Insert Position (LC 35)
Find first position where nums[i] ≥ target (exactly our find_left_boundary function).
Find Peak Element (LC 162)
Different paradigm but uses binary search on sorted-like properties.
Search in Rotated Sorted Array (LC 33)
Harder: array sorted then rotated. Requires modified binary search to find pivot first.
Find First and Last in Sorted Array with Duplicates Allowed K Missing
Variant: Return indices even if up to K elements between boundaries ≠ target. Requires counting mismatches.

Interview Cheat Sheet

Always Mention First:

“Since the array is sorted, we can use binary search to achieve O(log n) time”
“We need two binary searches: one for left boundary, one for right boundary”
“Edge cases: empty array, target not found, single element, all elements equal”

Common Follow-ups:

“How would you implement this in a language without built-in binary search?”
“What if the array had floating-point numbers?”
“How would you test this function?”
“Can you optimize to use only one binary search?” (Answer: You could but it’s more complex and same asymptotic complexity)

Testing Strategy:

Empty array
Single element array (equal and not equal to target)
All elements identical
Target smaller/larger than all elements
Even/odd length arrays
Duplicates at beginning/end/middle

Optimization Notes:

Early exit: if nums[0] > target or nums[-1] < target, return [-1,-1]
Combine loops: Some implementations use one binary search to find any occurrence, then expand linearly → O(log n + k) where k is target count (good if duplicates are few)
Memory-constrained: Iterative binary search preferred over recursive to avoid stack usage

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