Home Arrays [Leetcode] – First and Last Index Sorted Array Solution

# [Leetcode] – First and Last Index Sorted Array Solution

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.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More