Find First and Last Position of Element in Sorted Array LeetCode Solution

Table of Contents

Problem Statement:

Find First and Last Position of Element in Sorted Array LeetCode Solution says that – 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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums is a non-decreasing array.
-10⁹ <= target <= 10⁹

ALGORITHM –

In order to Find the First and Last Position of the Element in the Sorted Array LeetCode Solution. First, we will focus on the first appearance of the target value and then will move forward to the last appearance. We will use Binary Search in this question.
First, we will focus on the first appearance of the target value. So we will find the middle at first and check if the middle element value is equal to the target if it is equal then we will check middle element must be greater than the middle -1 and we have to take one edge case here i.e if mid == target and it is present at zero position then we will return mid else -1.
Second, we will focus on the last appearance of the target value. So we will again do the same first find middle then check the element value is equal to the target if it is equal then we will check middle element must be smaller than the middle + 1 and we have to cover one more edge case here i.e if mid == target and it is present at last index of the array then we will return mid else -1.
At last we will return [first_appearance,second_appearance].
Hence, we will find the First and Last Position of the Element in a Sorted Array.

IMAGE –

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        x = self.first(nums,target)
        y = self.last(nums,target)
        
        return [x,y]
        
        
    def first(self,nums,target):
        low = 0
        high = len(nums)-1
        
        while(low <= high):
            mid = (low+high)//2
            if nums[mid] == target and (target > nums[mid-1] or mid == 0):
                return mid
            
            elif nums[mid] < target:
                low = mid+1
                
            
            else:
                high = mid-1
                
        return -1        
                
    def last(self,nums,target):
        low = 0
        high = len(nums)-1
        
        while(low <= high):
            mid = (low+high)//2
            
            if ((nums[mid] == target) and (mid == len(nums)-1 or nums[mid+1] > target)):
                return mid
            
            elif nums[mid] > target:
                high = mid-1
                
            else:
                low = mid + 1
                
        return -1

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        int[] arr = new int[2];
        int x =first(nums,target);
        int y =last(nums,target);
        
        arr[0] = x;
        arr[1] = y;
        return arr;
    }
    public int first(int[] nums,int target){
        int low=0;
        int high=nums.length-1;
        int idx=-1;
        while(low<=high){
            int mid=low+(high-low)/2;
            if(nums[mid]==target)idx=mid;
            if(target>nums[mid]){
                low=mid+1;
            }
            else{
                high=mid-1;
            }
        }
        return idx;
    }
    public int last(int[] nums,int target){
        int low=0;
        int high=nums.length-1;
        int idx=-1;
        while(low<=high){
            int mid=low+(high-low)/2;
            if(nums[mid]==target)idx=mid;
            if(target>=nums[mid]){
                low=mid+1;
            }
            else{
                high=mid-1;
            }
        }
        return idx;
    }
}

Complexity Analysis for Find First and Last Position of Element in Sorted Array LeetCode Solution

Time Complexity – O(LOGN), We have used Binary Search in this question.

Space Complexity – O(1), We haven’t taken any extra space.