[Solved]Find First and Last Position of Element in Sorted Array -34 C++,Java,Python -Microsoft,Google, Amazon,Media.net

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.

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]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Solution

Approach

We use a two-pointer approach, where low starts at the beginning of the array, and high starts at the end of the array.
We compare the elements at low and high with the target value.
If the element at low is less than the target, we increment low.
If the element at high is greater than the target, we decrement high.
If we find two elements equal to the target, we return their indices in the array as the result.
If we do not find any such pair, we return [-1, -1] to indicate that the target value is not present in the array.

Complexity

• Time complexity:
  o(n)
• Space complexity:
  o(1)

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> v;
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            if (nums[low] < target)
                low = low + 1;
            else if (nums[high] > target)
                high = high - 1;
            else if (nums[low] == target && nums[high] == target) {
                v.push_back(low);
                v.push_back(high);
                return {low, high};
            }
        }
        return {-1, -1};
    }
};

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            if (nums[low] < target) {
                low++;
            } else if (nums[high] > target) {
                high--;
            } else if (nums[low] == target && nums[high] == target) {
                result[0] = low;
                result[1] = high;
                return result;
            }
        }
        result[0] = -1;
        result[1] = -1;
        return result;
    }
}

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        low, high = 0, len(nums) - 1
        while low <= high:
            if nums[low] < target:
                low += 1
            elif nums[high] > target:
                high -= 1
            elif nums[low] == target and nums[high] == target:
                return [low, high]
        return [-1, -1]

Happy Learning – If you require any further information, feel free to contact me.