34. Find First and Last Position of Element in Sorted Array Leetcode Solution
Find First and Last Position of Element in Sorted Array Leetcode 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.
Find First and Last Position of Element in Sorted Array Leetcode Solution :
Constraints :
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is a non-decreasing array.
- -10^9 <= target <= 10^9
Example 1:
- Input: nums = [5,7,7,8,8,10], target = 6
- Output: [-1,-1]
Example 2:
- Input: nums = [], target = 0
- Output: [-1,-1]
- Binary search will trivially find the answer, but there’s a twist here.
- To find the first reference, we go to the left half of the array to find an even lower index with the target.
- Vice-versa, we go to the higher indices to find the last reference.
- 2 Calls to find two different references at different directions (dir)
Approach :
1st we checked if target is present in array or not using binary search, if not returned {-1,-1};
else using lower_bound we can have 1st appearnce of target index, and using upper_bound we can have idx of the number which is present in array and just greater than target, obviously will apper next after finishing of target value, so index of last appearcne of target will be upper_bound index -1, so we returned accordingly.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution { public: vector< int> searchRange(vector< int>& nums, int target) { if(binary_search(nums.begin(),nums.end(),target)) { int idx=lower_bound(nums.begin(),nums.end(),target)-nums.begin(); int idx1=upper_bound(nums.begin(),nums.end(),target)-nums.begin(); return {idx,idx1-1}; } return {-1,-1}; } };
class Solution { public int[] searchRange(int[] nums, int target) { int first = -1, last = -1; for(int i=0;i< nums.length;i++){ if(nums[i] == target){ if(first == -1){ first = i; } last = i; } } return new int[]{first, last}; } }
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: left = 0 right = len(nums)-1 l = [] while left < len(nums): if nums[left]==target: l.append(left) break left +=1 while right >=0: if nums[right]==target: l.append(right) break right -=1 if len(l) ==0: return [-1,-1] else: return l
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment