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

In this guide we will provide 34. Find First and Last Position of Element in Sorted Array LeetCode Solution with best time and space complexity. The solution to Find First and Last Position of Element in Sorted Array problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Find First and Last Position of Element in Sorted Array solution in C++
Find First and Last Position of Element in Sorted Array soution in Java
Find First and Last Position of Element in Sorted Array solution Python
Additional Resources

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

Problem Statement of Find First and Last Position of Element in Sorted Array

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]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

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

Complexity Analysis

Time Complexity: O(\log n)
Space Complexity: O(1)

34. Find First and Last Position of Element in Sorted Array LeetCode Solution in C++

class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    const int l = ranges::lower_bound(nums, target) - nums.begin();
    if (l == nums.size() || nums[l] != target)
      return {-1, -1};
    const int r = ranges::upper_bound(nums, target) - nums.begin() - 1;
    return {l, r};
  }
};
/* code provided by PROGIEZ */

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

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

  private int firstGreaterEqual(int[] A, int target) {
    int l = 0;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
// code provided by PROGIEZ

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

class Solution:
  def searchRange(self, nums: list[int], target: int) -> list[int]:
    l = bisect_left(nums, target)
    if l == len(nums) or nums[l] != target:
      return -1, -1
    r = bisect_right(nums, target) - 1
    return l, r
 #code by PROGIEZ