First and Last Occurrences

Problem Statement

Given a sorted array arr (which may contain duplicates), find the first and last occurrences of an element x.

If x is not present in the array, return [-1, -1].

Examples:

Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5
Output: [2, 5]
Input: arr = [1, 3, 5, 5, 5, 5, 7, 123, 125], x = 7
Output: [6, 6]
Input: arr = [1, 2, 3], x = 4
Output: [-1, -1]

Constraints:

1 ≤ arr.size() ≤ 10^6
1 ≤ arr[i], x ≤ 10^9

Approach: Binary Search

Since the array is sorted, binary search allows us to efficiently find the first and last occurrences of x.

Steps:

First Occurrence:
Perform binary search.
If arr[mid] == x, move the high pointer to mid - 1 to check if x occurs earlier.
Last Occurrence:
Perform binary search.
If arr[mid] == x, move the low pointer to mid + 1 to check if x occurs later.

This ensures O(log n) time complexity for each search, perfect for large arrays.

Python CODE

from typing import List

class Solution:
def find(self, arr: List[int], x: int) -> List[int]:
n = len(arr)

    # Find first occurrence
    first, last = -1, -1
    low, high = 0, n - 1

    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            first = mid
            high = mid - 1  # Move left to find first occurrence

    # If element not found
    if first == -1:
        return [-1, -1]

    # Find last occurrence
    low, high = first, n - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] > x:
            high = mid - 1
        else:
            last = mid
            low = mid + 1  # Move right to find last occurrence

    return [first, last]

How It Works:

Binary search allows skipping unnecessary elements.
First occurrence moves left when arr[mid] == x.
Last occurrence moves right when arr[mid] == x.
Handles no occurrence by returning [-1, -1].

Time Complexity: O(log n)
Space Complexity: O(1)

This approach is optimal for large arrays and demonstrates the power of binary search in sorted arrays.