Find First and Last Position of Element in Sorted Array medium

Problem Statement

Given a sorted array of integers nums and an integer target, return the indices of the first and last occurrences of target in nums. If target is not found in nums, 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] Explanation: The first occurrence of 8 is at index 3 and the last occurrence is at index 4.

Example 2

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Explanation: Because 6 does not exist in the array, we return [-1,-1].

Steps

The core idea is to use binary search twice: once to find the leftmost occurrence and once to find the rightmost occurrence of the target.

1. Find Leftmost Occurrence:
   • Perform a binary search. If the target is found, continue searching in the left half to see if there's an earlier occurrence. The search stops when we find the target and the element to its left is different or we've reached the beginning of the array.
2. Find Rightmost Occurrence:
   • Perform a binary search. If the target is found, continue searching in the right half to see if there's a later occurrence. The search stops when we find the target and the element to its right is different or we've reached the end of the array.
3. Return Results: If either search doesn't find the target, return [-1, -1]. Otherwise, return the indices of the leftmost and rightmost occurrences.

Explanation

The binary search approach ensures a time complexity of O(log n) because we are repeatedly halving the search space. The crucial part is modifying the standard binary search to find the extreme occurrences (leftmost and rightmost) by selectively searching in the left or right subarray depending on whether we've found a match.

Code

function searchRange(nums: number[], target: number): number[] {
    const leftmost = findLeftmost(nums, target);
    const rightmost = findRightmost(nums, target);

    return [leftmost, rightmost];
};

function findLeftmost(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    let leftmostIndex = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            leftmostIndex = mid;
            right = mid - 1; // Continue searching in the left half
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return leftmostIndex;
}

function findRightmost(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    let rightmostIndex = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            rightmostIndex = mid;
            left = mid + 1; // Continue searching in the right half
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return rightmostIndex;
}

Complexity

• Time Complexity: O(log n) - Due to the use of binary search.
• Space Complexity: O(1) - Constant extra space is used. The algorithm operates in-place.