Last updated on October 10th, 2024 at 02:13 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

Find First and Last Position of Element in Sorted Array 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]

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;        
    }
};

2. 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;        
    }
}

3. 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]    
};

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