Blogs Hub

by Sumit Chourasia | Oct 25, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Find First and Last Position of Element in Sorted Array - Array - Medium - LeetCode

Find First and Last Position of Element in Sorted Array - Array - Medium - LeetCode

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

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

Follow up: Could you 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

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        var res = new int[2]{-1,-1};
        int l = BinarySearchLeft(nums,target,0,nums.Length-1);
        if(l==-1){
            return res;
        }
        int r = BinarySearchRight(nums,target,0,nums.Length-1);
        
        res[0]=l;
        res[1]=r;
        return res;
    }
    
    private int BinarySearchRight(int[] nums, int target, int lo, int hi){
        if(lo > hi){
            return -1;
        }
        
        int mid = lo + (hi-lo)/2;
        if(nums.Length==0){
            return -1;
        }
        
        if(mid==nums.Length-1){
            if(nums[mid]==target){
                return mid;
            }
            else{
                return -1;
            }
        }
        else if(nums[mid] == target && nums[mid+1]!=target){
            return mid;
        }
        else if(nums[mid]<=target){
            lo = mid+1;
        }
        else if(nums[mid]>target){
            hi = mid-1;
        }
        
        return BinarySearchRight(nums,target,lo,hi);
    }
    
    private int BinarySearchLeft(int[] nums, int target, int lo, int hi){
        if(lo>hi){
            return -1;
        }
        
        int mid = lo + (hi - lo)/2;
        if(mid == 0){
            if(nums.Length==0){
                return -1;
            }            
            else if(nums[0]==target){
                return 0;
            }
            if((nums.Length==2 && nums[1]==target)){
                return 1;
            }
            else{
                return -1;
            }
        }
        else if(nums[mid]==target && nums[mid-1]!=target){
            return mid;
        }
        else if(nums[mid]>=target){
            hi = mid-1;
        }
        else if(nums[mid]<target){
            lo = mid+1;
        }
        
        return BinarySearchLeft(nums, target, lo, hi);
    }
}

Time Complexity: O(logn)

Space Complexity: O(1)

Contributed By: Sumit Chourasia
Subarray Sum Equals K - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Array Nesting - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Richest Customer Wealth - String - Easy - LeetCode