Find First and Last Position of Element in Sorted Array

LeetCode 34: Find First and Last Position of Element in Sorted Array Solution & Explanation

Problem Overview

TL;DR: To solve this in logarithmic time, perform two modified binary searches: one to locate the leftmost index of the target and another to locate the rightmost index.

The problem asks us to find the starting and ending indices of a specific target value within an array of integers sorted in non-decreasing order. If the target does not exist in the array, we must return [-1, -1]. This is the core challenge of LeetCode 34: Find First and Last Position of Element in Sorted Array, a classic interview question that tests the ability to modify standard search algorithms.

The critical constraint is that the algorithm must run in O(log n) time complexity. This immediately rules out linear scanning approaches.

Brute Force Approach for Find First and Last Position of Element in Sorted Array

The naive approach involves iterating through the array linearly to find the target.

1. Initialize first and last to -1.
2. Iterate through the array from index 0 to n-1.
3. The first time we encounter target, set first to the current index.
4. Every time we encounter target, update last to the current index (since the array is sorted, subsequent occurrences are always to the right).
5. Return [first, last].

Pseudo-code:

function bruteForce(nums, target):
    first = -1
    last = -1
    for i from 0 to length(nums) - 1:
        if nums[i] == target:
            if first == -1:
                first = i
            last = i
    return [first, last]

Time Complexity Analysis: The time complexity is O(n), where n is the number of elements in the array. In the worst case, we must traverse the entire array.

Why it fails: While this solution produces the correct output, it violates the explicit problem constraint requiring O(log n) runtime complexity. In a large dataset (up to $10^5$ elements), an O(n) solution is significantly slower than O(log n), and in an interview context, this solution would be considered suboptimal.

Algorithm Strategy: Binary Search Patterns

We will implement a helper function (or run the same logic twice) that performs a binary search. This function will take a parameter indicating whether we are searching for the first or last occurrence.

Strategy Steps:

1. Initialize Pointers: Set low = 0 and high = n - 1.
2. Maintain Candidate: Create a variable index = -1 to store the most recent index where nums[mid] == target.
3. Loop: While low <= high:
   • Calculate mid.
   • If nums[mid] < target: Move right (low = mid + 1).
   • If nums[mid] > target: Move left (high = mid - 1).
   • If nums[mid] == target:
     • Update index = mid.
     • Crucial Branch:
       • If searching for First Position, continue searching left (high = mid - 1).
       • If searching for Last Position, continue searching right (low = mid + 1).
4. Execute: Run this search twice. Once to find the start, once to find the end.
5. Return: The pair of indices found.

Execution Flow

Let's trace the algorithm with nums = [5, 7, 7, 8, 8, 10] and target = 8.

Pass 1: Find First Position

1. low=0, high=5, mid=2. nums[2] is 7. $7 < 8$, so low becomes 3.
2. low=3, high=5, mid=4. nums[4] is 8.
   • Target found. Store index = 4.
   • We want the first position, so we look left. high becomes 3.
3. low=3, high=3, mid=3. nums[3] is 8.
   • Target found. Store index = 3.
   • We want the first position, so we look left. high becomes 2.
4. low=3, high=2. Loop terminates. First Position = 3.

Pass 2: Find Last Position

1. low=0, high=5, mid=2. nums[2] is 7. $7 < 8$, so low becomes 3.
2. low=3, high=5, mid=4. nums[4] is 8.
   • Target found. Store index = 4.
   • We want the last position, so we look right. low becomes 5.
3. low=5, high=5, mid=5. nums[5] is 10. $10 > 8$, so high becomes 4.
4. low=5, high=4. Loop terminates. Last Position = 4.

Result: [3, 4].

Proof of Correctness

The correctness relies on the monotonicity of the sorted array.

1. Termination: The while (low <= high) loop is guaranteed to terminate because the search space reduces by roughly half in each iteration, eventually causing pointers to cross.
2. Completeness: If the target exists, nums[mid] == target will eventually be true.
3. Boundary Finding: By strictly moving high to mid - 1 after a match (when finding the first), we ensure that we never settle for a non-minimal index. We exhaustively verify that no target exists to the left of the current candidate. The symmetric logic applies to finding the last index.

Pattern Reuse Notes

The Binary Search - Find First/Last Occurrence pattern logic is directly applicable to several other problems. Understanding how to continue searching after a match is key to solving:

• LeetCode 658: Find K Closest Elements - Requires finding the "closest" element, which often involves finding the first element $\ge$ target (lower bound).
• LeetCode 35: Search Insert Position - This is essentially finding the "first" index where the value is greater than or equal to the target.

Reference Implementation

C++ Solution for LeetCode 34

1class Solution {
2public:
3    vector<int> searchRange(vector<int>& nums, int target) {
4        vector<int> result = {-1, -1};
5        result[0] = findBound(nums, target, true);  // Find first
6        if (result[0] == -1) return result;         // Target not found
7        result[1] = findBound(nums, target, false); // Find last
8        return result;
9    }
10
11private:
12    int findBound(vector<int>& nums, int target, bool isFirst) {
13        int left = 0, right = nums.size() - 1;
14        int boundIndex = -1;
15
16        while (left <= right) {
17            int mid = left + (right - left) / 2;
18
19            if (nums[mid] == target) {
20                boundIndex = mid;
21                // If finding first, narrow search to left half
22                if (isFirst) {
23                    right = mid - 1;
24                } 
25                // If finding last, narrow search to right half
26                else {
27                    left = mid + 1;
28                }
29            } else if (nums[mid] < target) {
30                left = mid + 1;
31            } else {
32                right = mid - 1;
33            }
34        }
35        return boundIndex;
36    }
37};

Java Solution for LeetCode 34

1class Solution {
2    public int[] searchRange(int[] nums, int target) {
3        int[] result = new int[]{-1, -1};
4        result[0] = findBound(nums, target, true);
5        
6        // If the target isn't found once, it won't be found twice
7        if (result[0] == -1) {
8            return result;
9        }
10        
11        result[1] = findBound(nums, target, false);
12        return result;
13    }
14
15    private int findBound(int[] nums, int target, boolean isFirst) {
16        int left = 0;
17        int right = nums.length - 1;
18        int index = -1;
19
20        while (left <= right) {
21            int mid = left + (right - left) / 2;
22
23            if (nums[mid] == target) {
24                index = mid;
25                if (isFirst) {
26                    right = mid - 1; // Continue searching left
27                } else {
28                    left = mid + 1;  // Continue searching right
29                }
30            } else if (nums[mid] < target) {
31                left = mid + 1;
32            } else {
33                right = mid - 1;
34            }
35        }
36
37        return index;
38    }
39}

Python Solution for LeetCode 34

1class Solution:
2    def searchRange(self, nums: List[int], target: int) -> List[int]:
3        
4        def find_bound(is_first: bool) -> int:
5            left, right = 0, len(nums) - 1
6            bound_index = -1
7            
8            while left <= right:
9                mid = left + (right - left) // 2
10                
11                if nums[mid] == target:
12                    bound_index = mid
13                    if is_first:
14                        right = mid - 1  # Narrow search to left
15                    else:
16                        left = mid + 1   # Narrow search to right
17                elif nums[mid] < target:
18                    left = mid + 1
19                else:
20                    right = mid - 1
21            
22            return bound_index
23
24        start = find_bound(True)
25        if start == -1:
26            return [-1, -1]
27        
28        end = find_bound(False)
29        return [start, end]