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.

jump game leetcode

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]
Intuition :
  • 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 :

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription