Leetcode 34. Find First and Last Position of Element in Sorted Array

Accepted Code

Problem Statement

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Test Cases

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

Approach

We need to search for a target inside the given sorted array and need to track the first and last occurrence of that target.

We can normally do a linear search on the given array and search for that target. Track the first and last occurrence and just store them. Here our time complexity will be O(n) where n = length of array.

But can’t we make use of the fact that the array is sorted. If the array is sorted and our mission is something related to searching inside the array and track something, we can always go for binary search.

We need to track the left most target and right most target. So we need 2 binary search on the given array.

1. One binary search will search for the target + we try to find the left most occurrence of that target.
2. Another binary search will again do the search for the target + we try to find the right most occurrence of that target.

private int findLeftMost(int [] nums, int target) {
        int length = nums.length;
        int low = 0;
        int high = length - 1;
        int index = -1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (nums[middle] == target) {
                index = middle;
                high = middle - 1;
            }
            else if (nums[middle] < target){
                low = middle + 1;
            }
            else {
                high = middle - 1;
            }
        }
        return index;
    }
private int findRightMost(int [] nums, int target) {
        int length = nums.length;
        int low = 0;
        int high = length - 1;
        int index = -1;
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (nums[middle] == target) {
                index = middle;
                low = middle + 1;
            }
            else if (nums[middle] > target){
                high = middle - 1;
            }
            else {
                low = middle + 1;
            }
        }
        return index;
    }

These are the two binary search that will come in handy. So what basically happens here.

In the first binary search, we are returning the index where the target occurs the very first time. If we sees the target, we move our right pointer to middle — 1 as the first occurrence of that target will be towards the left most area.

In the second binary search, we are returning the index where the target occurs the very last time. If we sees the target, we move our left pointer to middle +1 as the last occurrence of that target will be towards the right most area.

Algorithm

1. Check whether the given array is empty or not.(Edge case).
2. Do the first binary search to find the left most index.
3. If it is -1, then that target is not present, return {-1, -1}.
4. Otherwise, do the second binary search to find the right most index.
5. Return {leftMostIndex, rightMostIndex}.

Time Complexity

Here we are doing binary search 2 times.The time complexity will beO(logn) + O(logn) where n = length of array.

We are not making use of any extra space, so space complexity will be O(1).

Code

Java Code

LeetCodeTopInterviewQuestions/25_Find_First_And_Last_Position_Of_Element_In_Sorted_Array.java at…