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.