# 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.

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]
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.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## 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