Find first and last positions of an element in a sorted array

Problem Statement

Given a sorted array of integers and a target value, find the starting and ending position of the target value in the array. If the target is not found, return [-1, -1].

Constraints:

• Array is sorted in non-decreasing order
• Target may appear multiple times or not at all

Example:

• Input: nums = [5, 7, 7, 8, 8, 10], target = 8
• Output: [3, 4]
• Explanation: 8 first appears at index 3 and last appears at index 4

Example 2:

• Input: nums = [5, 7, 7, 8, 8, 10], target = 6
• Output: [-1, -1]
• Explanation: 6 is not present in the array

Approach 1: Brute Force (Linear Scan)

Intuition

Scan through the entire array to find the first and last occurrence of the target element.

Algorithm

1. Initialize first = -1 and last = -1
2. Traverse the array from left to right
3. When target is found for the first time, set first = current index
4. Keep updating last whenever target is found
5. Return [first, last]

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1, last = -1;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (first == -1) {
                    first = i;
                }
                last = i;
            }
        }
        
        return new int[]{first, last};
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only using two variables

Approach 2: Binary Search (Optimal)

Intuition

Since the array is sorted, we can use binary search to find the first and last positions efficiently. We perform two binary searches: one to find the leftmost (first) occurrence and another to find the rightmost (last) occurrence.

Algorithm

1. Find First Position:

   • Binary search but continue searching left even when target is found
   • Update result and search in left half when target is found

2. Find Last Position:

   • Binary search but continue searching right even when target is found
   • Update result and search in right half when target is found

public class Solution {
    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int first = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                first = mid;
                right = mid - 1;  // Continue searching left
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return first;
    }
    
    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int last = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                last = mid;
                left = mid + 1;  // Continue searching right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return last;
    }
    
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirst(nums, target), findLast(nums, target)};
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(log n) - Two binary searches
• Space Complexity: O(1) - Only using pointers

Using STL/Built-in Functions

Key Takeaways

1. Binary Search Variations: This problem demonstrates how to modify binary search to find boundaries instead of just presence
2. Lower Bound vs Upper Bound: Understanding the difference helps in many range-based problems
3. Continue Searching: Key insight is to not stop when target is found, but continue in the appropriate direction
4. Two Searches: Separate searches for first and last positions keeps the logic clean and easy to understand
5. Edge Cases: Handle empty arrays and targets not present in the array
6. STL Functions: lower_bound and upper_bound in C++ provide this functionality built-in