LeetCode 34: Find First and Last Position of Element in Sorted Array Solution in Python Explained

Problem Statement

LeetCode 34, Find First and Last Position of Element in Sorted Array, is a medium-level problem where you’re given a sorted array of integers nums in non-decreasing order and a target integer target. Your task is to return the starting and ending positions of target in nums as a list [start, end]. If target is not found, return [-1, -1]. The solution must run in O(log n) time complexity due to the sorted nature of the array.

Constraints

  • 0 <= nums.length <= 10^5: Array length is between 0 and 100,000.
  • -10^9 <= nums[i], target <= 10^9: Elements and target are within this range.
  • nums is sorted in non-decreasing order (may contain duplicates).

Example

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Explanation: 8 appears at indices 3 and 4.

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Explanation: 6 isn’t in the array.

Input: nums = [], target = 0
Output: [-1,-1]
Explanation: Empty array has no target.

Understanding the Problem

How do you solve LeetCode 34: Find First and Last Position of Element in Sorted Array in Python? For nums = [5,7,7,8,8,10] and target = 8, you need to find the range [3, 4] where 8 appears. Since the array is sorted, binary search can locate these boundaries efficiently. We’ll explore two approaches: a Binary Search with Two Passes Solution (optimal and primary) and an Alternative with Linear Search (simple but slower). The binary search method uses two searches to find the first and last occurrences in O(log n) time.

Solution 1: Binary Search with Two Passes Approach (Primary)

Explanation

Perform two binary searches: one to find the leftmost (first) occurrence of target and another for the rightmost (last). Modify the standard binary search to bias towards the left or right boundary when duplicates are encountered.

Here’s a visual for [5,7,7,8,8,10], target = 8:

First pass (leftmost): mid = 2 (7), too low, mid = 4 (8), go left, mid = 3 (8), found
Second pass (rightmost): mid = 2 (7), too low, mid = 4 (8), go right, mid = 4 (8), found
Result: [3, 4]
  1. Handle Edge Case.
  • If array is empty, return [-1, -1].
  1. Find Leftmost.
  • Binary search, move left when target found.
  1. Find Rightmost.
  • Binary search, move right when target found.
  1. Return Range.

Step-by-Step Example

Example 1: nums = [5,7,7,8,8,10], target = 8

We need [3, 4].

  • Goal: Find first and last positions of 8.
  • Result for Reference: [3, 4].
  • Start: nums = [5,7,7,8,8,10], n = 6.
  • Step 1: Check empty, not empty, proceed.
  • Step 2: Find leftmost 8.
    • left = 0, right = 5, mid = 2, nums[2] = 7 < 8, left = 3.
    • left = 3, right = 5, mid = 4, nums[4] = 8, target found, right = 3.
    • left = 3, right = 3, mid = 3, nums[3] = 8, target found, right = 2.
    • left = 3 > right = 2, stop, leftmost = 3.
  • Step 3: Find rightmost 8.
    • left = 0, right = 5, mid = 2, nums[2] = 7 < 8, left = 3.
    • left = 3, right = 5, mid = 4, nums[4] = 8, target found, left = 5.
    • left = 5, right = 5, mid = 5, nums[5] = 10 > 8, right = 4.
    • left = 5 > right = 4, stop, rightmost = 4.
  • Finish: Return [3, 4].

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

We need [-1, -1].

  • Goal: Find range of 6.
  • Start: Leftmost search.
    • left = 0, right = 5, mid = 2, 7 > 6, right = 1.
    • left = 0, right = 1, mid = 0, 5 < 6, left = 1.
    • left = 1, right = 1, mid = 1, 7 > 6, right = 0.
    • left = 1 > right = 0, stop, no 6 found.
  • Finish: Return [-1, -1] (early exit possible).

Here’s the Python code with line-by-line explanation:

def searchRange(nums: list[int], target: int) -> list[int]:
    # Line 1: Handle empty array
    if not nums:
        return [-1, -1]

    # Line 2: Helper for binary search
    def findBound(is_left: bool) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            # Line 3: Compare with target
            if nums[mid] == target:
                # Line 4: Bias left or right
                if is_left:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        # Line 5: Return boundary
        return left if is_left else right

    # Line 6: Find leftmost and rightmost
    leftmost = findBound(True)
    # Line 7: Early exit if target not found
    if leftmost >= len(nums) or nums[leftmost] != target:
        return [-1, -1]
    rightmost = findBound(False)

    # Line 8: Return range
    return [leftmost, rightmost]

Alternative: Linear Search Approach

Explanation

Scan the array linearly to find the first and last occurrences of target. This is straightforward but O(n), not meeting the O(log n) requirement.

  1. Scan Array.
  2. Track First and Last.
  3. Return Range.

Step-by-Step Example (Alternative)

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

  • Goal: [3, 4].
  • Step 1: i = 0, 5 ≠ 8, continue.
  • Step 2: i = 3, 8 = 8, first = 3.
  • Step 3: i = 4, 8 = 8, last = 4.
  • Finish: Return [3, 4].

How the Code Works (Linear)

def searchRangeLinear(nums: list[int], target: int) -> list[int]:
    # Line 1: Handle empty array
    if not nums:
        return [-1, -1]

    # Line 2: Track boundaries
    first = -1
    last = -1
    # Line 3: Linear scan
    for i in range(len(nums)):
        if nums[i] == target:
            if first == -1:
                first = i
            last = i

    # Line 4: Return result
    return [first, last]

Complexity

  • Binary Search:
    • Time: O(log n) – Two binary searches.
    • Space: O(1) – No extra space.
  • Linear Search:
    • Time: O(n) – Single pass.
    • Space: O(1).

Efficiency Notes

Binary Search achieves O(log n), ideal for LeetCode 34, while Linear Search (O(n)) is too slow but easier for beginners.

Key Insights

Tips to master LeetCode 34:

  • Two Searches: Split the problem into first and last.
  • Bias the Search: Adjust binary search for boundaries.
  • Sorted Advantage: Leverage non-decreasing order.

Additional Example

For nums = [1,2,2,2,3], target = 2:

  • Goal: [1, 3].
  • Binary: Leftmost = 1, Rightmost = 3.
  • Result: [1, 3].

Edge Cases

  • Empty Array: [] – Return [-1, -1].
  • No Target: [1,2,3], target = 4 – Return [-1, -1].
  • All Same: [2,2,2], target = 2 – Return [0, 2].

Final Thoughts

The Binary Search with Two Passes solution is a winner for LeetCode 34 in Python—elegant, efficient, and logarithmic. For a related challenge, check out LeetCode 33: Search in Rotated Sorted Array to test your binary search skills further! Ready to ace it? Solve LeetCode 34 on LeetCode now and try arrays like [1,2,2,3] or [5,5,5] to perfect your boundary-finding skills. Dive in and crush it!