💡Solving LeetCode 34: Find First and Last Position of Element in a Sorted Array

Problem Statement

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

The problem asks for an efficient solution with a time complexity of O(log n), which hints at using binary search.

Example:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

In this example, the target 8 is found at positions 3 and 4.

Edge Case:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Here, the target 6 is not found in the array, so the output is [-1,-1].

Approach

The problem can be broken down into two main tasks:

1. Finding the leftmost (first) position of the target.
2. Finding the rightmost (last) position of the target.

Since the array is sorted, we can leverage binary search to efficiently find these positions. We will write two helper functions to achieve this:

1. findLeftBound(): This function will perform a binary search to find the first occurrence of the target.
2. findRightBound(): This function will perform a binary search to find the last occurrence of the target.

After finding both boundaries, we will return them in an array. If the target is not found in the array, both functions will return -1.

Solution Code

Here is the complete Java implementation of the solution:

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] nums = {5, 6, 7, 7, 7, 8, 9};
        int target = 7;

        int[] ans = searchRange(nums, target);
        System.out.println(Arrays.toString(ans));
    }

    public static int[] searchRange(int[] nums, int target) {
        int left = findLeftBound(nums, target);
        int right = findRightBound(nums, target);

        return new int[]{left, right};
    }

    static int findLeftBound(int[] nums, int target) {
        int index = -1;
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                index = mid;
                end = mid - 1;  // Move left to find the leftmost target
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return index;
    }

    static int findRightBound(int[] nums, int target) {
        int index = -1;
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                index = mid;
                start = mid + 1;  // Move right to find the rightmost target
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return index;
    }
}

Explanation

1. searchRange Function:

   • This function is the main entry point for finding the range of the target. It calls two helper functions, findLeftBound and findRightBound, and returns their results in an array.

2. findLeftBound Function:

   • The goal of this function is to find the first occurrence of the target.
   • If nums[mid] equals target, we update index and move the end pointer to mid - 1 to continue searching on the left side.
   • If nums[mid] is less than the target, we move the start pointer to mid + 1 to search the right side.
   • If nums[mid] is greater than the target, we move the end pointer to mid - 1 to search the left side.
   • This continues until start exceeds end.

3. findRightBound Function:

   • The goal of this function is to find the last occurrence of the target.
   • The logic is similar to findLeftBound, except that when we find the target, we move the start pointer to mid + 1 to continue searching on the right side.

4. Edge Cases:

   • If the target is not found, both findLeftBound and findRightBound return -1, resulting in [-1, -1] being returned by searchRange.
   • If the array is empty, both functions will return -1, which is handled properly.

Time Complexity

The time complexity of this solution is O(log n) for each of the helper functions due to the binary search. Since we call two binary searches, the total time complexity remains O(log n), which meets the problem's efficiency requirements.

Happy coding! 🚀