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

Last updated on February 22nd, 2024 at 04:06 am

Here, We see Find First and Last Position of Element in Sorted Array Leetcode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Problem Statement

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

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

Find First and Last Position of Element in Sorted Array Leetcode Solution C++

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int idx1 = lower_bound(nums, target);
int idx2 = lower_bound(nums, target+1)-1;
if (idx1 < nums.size() && nums[idx1] == target)
return {idx1, idx2};
else
return {-1, -1};
}

int lower_bound(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while (l <= r) {
int mid = (r-l)/2+l;
if (nums[mid] < target)
l = mid+1;
else
r = mid-1;
}
return l;
}
};
```Code language: C++ (cpp)```

Find First and Last Position of Element in Sorted Array Leetcode Solution Java

``````class Solution {
public int[] searchRange(int[] nums, int target) {
int start = Solution.firstGreaterEqual(nums, target);
if (start == nums.length || nums[start] != target) {
return new int[]{-1, -1};
}
return new int[]{start, Solution.firstGreaterEqual(nums, target + 1) - 1};
}

//find the first number that is greater than or equal to target.
//could return A.length if target is greater than A[A.length-1].
//actually this is the same as lower_bound in C++ STL.
private static int firstGreaterEqual(int[] nums, int target) {
int low = 0, high = nums.length;
while (low < high) {
int mid = low + ((high - low) >> 1);
//low <= mid < high
if (nums[mid] < target) {
low = mid + 1;
} else {
//should not be mid-1 when A[mid]==target.
//could be mid even if A[mid]>target because mid<high.
high = mid;
}
}
return low;
}
}
```Code language: Java (java)```

Find First and Last Position of Element in Sorted Array Leetcode Solution JavaScript

``````var searchRange = function(nums, target) {
const find = (target, arr, left=0, right=arr.length) => {
while (left <= right) {
let mid = left + right >> 1
if (arr[mid] < target) left = mid + 1
else right = mid - 1
}
return left
}
let targetleft = find(target, nums)
if (nums[targetleft] !== target) return [-1,-1]
return [targetleft, find(target+1, nums, targetleft) - 1]
};
```Code language: JavaScript (javascript)```

Find First and Last Position of Element in Sorted Array Leetcode Solution Python

``````class Solution(object):
def searchRange(self, nums, target):
targetleft = bisect_left(nums, target)
if targetleft == len(nums) or nums[targetleft] != target: return [-1, -1]
return [targetleft, bisect_right(nums, target) - 1]
```Code language: Python (python)```
Scroll to Top