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

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.

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]

• C++ Solution
• Java Solution
• JavaScript Solution
• Python Solution

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)