Mohith

Posted on Mar 20

First and Last Occurrence – CA19

#algorithms #coding #computerscience #tutorial

My Thinking and Approach

Introduction

In this problem, I was given a sorted array with possible duplicates, and I needed to find the first and last occurrence of a given element x.

At first, it looked like a simple search problem, but since the array is sorted, I realized I could optimize it.

Problem Understanding

Given a sorted array
Find:
- First occurrence of x
- Last occurrence of x
If not found, return [-1, -1]

My Initial Thought

Initially, I thought:

Traverse the entire array
Store first and last index when x is found

But this approach takes:

Time: O(n)

Since the array is sorted, I thought of a better approach.

Optimized Thinking (Binary Search)

Because the array is sorted, I can use Binary Search to find:

First occurrence
Last occurrence

My Approach

Step 1: Find First Occurrence

Use binary search
When arr[mid] == x:
- Store index
- Move left (high = mid - 1)

Step 2: Find Last Occurrence

Again use binary search
When arr[mid] == x:
- Store index
- Move right (low = mid + 1)

Code (Java)

import java.util.ArrayList;

class Solution {
    ArrayList<Integer> find(int arr[], int x) {
        ArrayList<Integer> result = new ArrayList<>();

        int first = findFirst(arr, x);
        int last = findLast(arr, x);

        result.add(first);
        result.add(last);

        return result;
    }

    private int findFirst(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == x) {
                ans = mid;
                high = mid - 1;
            } else if (arr[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return ans;
    }

    private int findLast(int[] arr, int x) {
        int low = 0, high = arr.length - 1;
        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == x) {
                ans = mid;
                low = mid + 1;
            } else if (arr[mid] < x) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return ans;
    }
}

Example Walkthrough

Example 1

Input:
arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5

First occurrence → index 2
Last occurrence → index 5

Output:
[2, 5]

Example 2

Input:
arr = [1, 3, 5, 5, 5, 5, 7, 123, 125], x = 7

Output:
[6, 6]

Example 3

Input:
arr = [1, 2, 3], x = 4

Output:
[-1, -1]

Complexity Analysis

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

Key Takeaways

Binary Search can be modified for different use cases
Always take advantage of sorted arrays
Finding boundaries (first/last occurrence) is a common pattern

Conclusion

This problem helped me understand how to extend binary search beyond simple searching. It improved my ability to think about edge cases and optimize solutions using the properties of sorted data.

DEV Community