[Leetcode] – First and Last Index Sorted Array Solution

1.7K

A good idea will be to understand this problem statement first. We are given a sorted array and a target element. We need to return the first and last index of this target element in the sorted array. The array has a 0 based indexing, and if the element is not found we need to return a [-1, -1].

Let us look at some sample test cases:

Input: [ 5, 7, 7, 8, 8, 10 ]
Target: 8
Output: [3, 4]
Explanation:
The first occurrence of element 8 is at index 3 and the last occurrence is at index 4

Input: [ 5, 7, 7, 8, 8, 10 ]
Target: 6
Output: [-1, -1]
Explanation:
We cannot find 6 in the array.

Brute Force Method:

The most naive way or the brute force method to solve this problem is very simple. We know the index of each element in the array. So we can devise a way to find the first and last occurrence.

• Start iterating through the array from the beginning and match each element to the target element.
• If the element matches, we get the first index. Mark it and move ahead.
• Keep matching the elements until we see a mismatch.
• This is the last index of the element.

As soon as you have a mismatch, just exit the loop iteration and we have our answer of the first and last index. But this approach is not scalable. In a worst case scenario, we will have to scan the entire array.

Efficient Solution:

In our previous approach, we did not use any extra space, and the time complexity is also O(n). When we think about improving it, we tend to find a logarithmic time complexity. This gives you some idea.

As soon as you see a sorted array, the first thing that should come to your mind is the binary search algorithm. We have to find the first and last index in a sorted array. This is same as searching for that element.

All we have to do is apply a modified version of the binary search algorithm. A traditional approach will be to search for the exact target element. But in this scenario we have to apply this search technique 2 times.

• Find the first occurrence by searching for a the target element such that the left element is smaller or null.
• Find the last occurrence by searching for a target element such that the element to right of it is greater or null.

For example, let us say we have an example array:
[0, 0, 1, 1, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5, 7, 7]
Target element = 5

When we start applying binary search for 5, the array will be divided into 2 halves.

The trick here is to now search for an occurrence of 5 with a smaller element to the left in the left half of the array.

Once we get this, repeat the same process to search for an occurrence of 5 with a larger element to the right in the other half.

This is another example of the Divide and Conquer algorithmic paradigm.

Code:

public int[] searchRange(int[] nums, int target) {

    int left = findLeftBound(nums, target);
    int right = findRightBound(nums, target);

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

  private int findLeftBound(int[] nums, int target) {
    int index = -1, low = 0, high = nums.length - 1;

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

      if (nums[mid] == target) {
        index = mid;
        high = mid - 1; // Look in the left sub-array
      }
      else if (nums[mid] < target)
        low = mid + 1;
      else
        high = mid - 1;
    }

    return index;
  }

  private int findRightBound(int[] nums, int target) {
    int index = -1, low = 0, high = nums.length - 1;

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

      if (nums[mid] == target) {
        index = mid;
        low = mid + 1; // Look in the right sub-array
      }
      else if (nums[mid] < target)
        low = mid + 1;
      else
        high = mid - 1;
    }

    return index;
  }
Code language: Java (java)

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

You can also find the code and test cases on GitHub.

Video Explanation: