Last updated on January 29th, 2025 at 02:25 am
Here, we see a Find First and Last Position of Element in Sorted Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Binary Search
Companies
Level of Question
Medium
Find First and Last Position of Element in Sorted Array LeetCode Solution
Table of Contents
1. 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]
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is Modified Binary Search. This pattern involves using binary search with slight modifications to solve problems like finding specific elements, ranges, or conditions in sorted arrays. The code leverages binary search to efficiently find the lower and upper bounds of the target value in a sorted array.
3. Code Implementation in Different Languages
3.1 Find First and Last Position of Element in Sorted Array 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;
}
};
3.2 Find First and Last Position of Element in Sorted Array 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.3 Find First and Last Position of Element in Sorted Array 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]
};
3.4 Find First and Last Position of Element in Sorted Array 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]
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(log n) | O(1) |
| Java | O(log n) | O(1) |
| JavaScript | O(log n) | O(1) |
| Python | O(log n) | O(1) |
- Time Complexity: The binary search is performed twice (once for
targetand once fortarget+1), but since each binary search is O(log n), the overall time complexity remains O(log n). - Space Complexity: The space complexity is O(1) because the algorithm does not use any additional data structures or recursive calls.
- Efficiency: This approach is highly efficient for sorted arrays, as it avoids a linear scan and directly narrows down the search space using binary search.