Find First and Last Position of Element in Sorted Array

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

Problem

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.

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 <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

spoiler ALERT !!!

If you have come to see the solution before trying to solve it yourself, this really won’t help you, promise! If that is the case, we will recommend, please go back and first try it yourself. If you can’t solve it after (at least)an hour of thinking and trying, please come back! 🙂 You can solve it here.

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

Solution of Find First and Last Position of Element in Sorted Array (Leetcode 34)

We will see two approaches to solve this problem, Linear and Binary search.

Approach-1: Linear Search

Analysis

In linear search approach, we can run a for loop through the array. For each element, we check if the element is equal to the target we are looking for. If the target is found, we save its index to a variable (which was initialized by -1). This is the first position of our target in the array.

We then continue to the loop. If the target is found again, we save its index to another variable (which was initialized by -1 as well) and still continue to the loop. We keep updating the second variable (with target’s index) until we keep finding target in the array.

Finally, we return the two indices. Pretty 🤩 straight forward, right?

But wait, what will happen if the target is there only once? In that case, first and last position should have the same index value, right?

For this case, we can simply check if we found the firs position (by checking if the value is -1 or not) or not. If we found first position and we found the value of last position is still -1, that means the target is in the array for only once. In that case, we will update last position with the value of first position and return them both.

Below is a simple pseudocode for this approach.

function search(target, nums[]){
   first_position = -1
   last_position = -1
   for each i as index of nums array{
       if (nums[i] == target and first_position == -1){ /* target is seen for the first time. So, first_position should have the index */
             first_position = i;
          }
       else if (nums[i] == target){ /* target is seen but NOT for the first time. So, last_position will get updated for each time target is seen */
             last_position = i; 
          }
   }
   
   if(first_position != -1 and last_position == -1)
      last_position = first_position;

   return {first_position, last_position};   
}

Time Complexity

Since we are traversing each element of the array, in worst case, we will have to go up to the end of array. If there are n elements in the array, we will have to search n elements in worst case. Hence, the time complexity is O(n).

Space Complexity

No extra space (that is dependent on the input size) is being used here. So the space complexity is O(1).

Approach-2: Binary Search with little tweak! 😒

Linear search worked well, but there is a better way to improve time complexity to O(logn) by applying binary search with little tweak! Please bear in mind a little tip, when the array is sorted and we are asked to find something from that array, in many (or most) of the cases the thought process will direct us towards binary search algorithm!

Analysis

We know that applying binary search we can find the position of target element. What if after getting the first occurrence of the target we do not stop? Rather move towards left to get the target element again (if there is any)? Or move towards right to get the target element again (if there is any)?

1) Let’s say we want to find the first occurrence of 30 in the array below. The array has 9 elements indexed from 0 to 8. We have a variable first_position initialized with -1. This will hold the index of first occurrence of target element.

2) We have left and right variables that contain the first and last element of the array. We calculate the mid element as mid = left + (right – left) / 2.

At first we select index 4 as the mid element of binary search and find that it contains our desired target 30. If we were to find any index that have target element, we could stop ✋ searching and return the result. But since we want to know the first occurrence of target, we want to move left to see if there is any more occurrence of target in left or not.

However, there might not be any more occurrence of target in left and this occurrence might be the first occurrence (which we do not know beforehand until completing the loop). So, we keep updated first_position with current index to be in the safe side.

To move towards left, we will update right = mid – 1.

3) At this point we are considering only the part from index 0 to 3 and our right index is 3 now after updating. Our mid is now 1 containing 20 which is smaller than target. So, we will move towards right by updating left = mid + 1.

Since we didn’t find the target element here, we do not update first_position and it still holds index 4 as found before.

4) At this stage, we found target again and updated first_position. Since, target is found again and we want to see if there is anymore in left side, we move towards left updating right = mid – 1.

5) Now, right is less than left which breaks our binary search loop. We accomplish our mission by having first_position = 2 in hour hand!

If you have understood the analysis so far and think a little bit, you might be able to answer how to find the last position. If not, we suggest. you read the analysis again and think more! If you find the explanation is not good enough, leave your comments please. We are always open to improvement.

How to find the last position?

To find the last position, we apply the same logic as before. The only difference is, after finding the target element, instead of moving towards left, we will move towards right this time.

We can do this by simply updating left = mid + 1.

Time Complexity

Since we are using binary search algorithm with modification, the time complexity is still O(logn).

Space Complexity

No extra space (that might be dependent on input size) is required for this solutions, hence O(1) complexity for space.

Comparison Between Two Approaches

	LINEAR search	BINARY search
Time complexity	O(n)	O(logn)
Space Complexity	O(1)	O(1)

So, Binary search is the winner for time complexity.

Companies asked this question

Facebook, Google, Amazon, Microsoft, Twitter, Linkedin and many more!

Code

C++ Code

/* C++ solution of problem: Find First and Last Position of Element in Sorted Array (Leetcode 34) */

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        
        vector<int> ans;
        int left = 0;
        int right = nums.size() - 1;
        
        int first_position = -1;
        int last_position = -1;
        
        //Fidn the first occurance of target
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                first_position = mid;
                right = mid - 1;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        ans.push_back(first_position);
        
        //Fidn the last occurance of target
        left = 0;
        right = nums.size() - 1;
        
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                last_position = mid;
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        ans.push_back(last_position);
        return ans;    
    }
};

Java Code

/* Java solution of problem: Find First and Last Position of Element in Sorted Array (Leetcode 34) */
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        int left = 0;
        int right = nums.length - 1;
        
        int first_position = -1;
        int last_position = -1;
        
        //Fidn the first occurance of target
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                first_position = mid;
                right = mid - 1;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        ans[0] = first_position;
        
        //Fidn the last occurance of target
        left = 0;
        right = nums.length - 1;
        
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                last_position = mid;
                left = mid + 1;
            }
            else if(nums[mid] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        ans[1] = last_position;
        return ans;
    }
}

Python Code

#Python solution of problem: Find First and Last Position of Element in Sorted Array (Leetcode 34)
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        left, right = 0, n-1
        first_position = -1
        last_position = -1
        
        while left <= right:
            mid = left + (right - left) / 2
            if nums[mid] == target:
                first_position = mid
                right = mid - 1
            elif nums[mid] &lt; target:
                left = mid + 1
            else:
                right = mid - 1
        
        left = 0
        right = n - 1
        
        while left <= right:
            mid = left + (right - left) / 2
            if nums[mid] == target:
                last_position = mid
                left = mid + 1
            elif nums[mid] &lt; target:
                left = mid + 1
            else:
                right = mid - 1
        
        ans = []
        ans.append(first_position)
        ans.append(last_position)
        
        return ans

Similar Problems to solve

If you want to solve more problems like this to improve your problem solving skills, here is the list:

1. First Bad Version

Conclusion

Hope you enjoyed this blog. If you do, please feel free to write your comments. If you do not enjoy this, please tell us how we can improve! Thanks a lot, Happy Coding! 🙂