0000 - 0099
0034 - Find First and Last Position of Element in Sorted Array (Medium)
Problem Link
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
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].
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 <= 10^5-10^9 <= nums[i] <= 10^9numsis a non-decreasing array.-10^9 <= target <= 10^9
Approach 1: Binary Search
:::info Prerequisite
:::
class Solution {
public:
int getFirstPosition(vector<int>& nums, int target) {
int n = nums.size(), l = 0, r = n - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (target > nums[m]) l = m + 1;
else r = m;
}
return nums[l] == target ? l : -1;
}
int getLastPosition(vector<int>& nums, int target) {
int n = nums.size(), l = 0, r = n - 1;
while (l < r) {
int m = l + (r - l + 1) / 2;
if (target < nums[m]) r = m - 1;
else l = m;
}
return nums[l] == target ? l : -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
// handle edge case
if ((int) nums.size() == 0) return {-1, -1};
// return the lower bound and upper bound - 1
return vector<int> {
// if the first position is -1, we can return ans directly
// see Approach 2: Optimal Binary Search
getFirstPosition(nums, target),
getLastPosition(nums, target)
};
}
};class Solution {
public int[] searchRange(int[] nums, int target) {
int start = 0, end = nums.length - 1, firstelement = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
firstelement = mid;
end = mid - 1;
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
start = 0;
end = nums.length - 1;
int endelement = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
endelement = mid;
start = mid + 1;
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return new int[] { firstelement, endelement };
}
}/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
let l = 0;
let r = nums.length - 1;
while (l <= r) {
let mid = Math.floor((l + r) / 2);
if (nums[l] == target && nums[r] == target) {
return [l, r];
}
if (nums[mid] > target) {
r = mid - 1;
} else if (nums[mid] < target) {
l = mid + 1;
} else {
if (nums[l] != target) l++;
if (nums[r] != target) r--;
}
}
return [-1, -1];
};class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[l] == nums[r] == target:
return [l, r]
if nums[mid] > target:
r = mid - 1
elif nums[mid] < target:
l = mid + 1
else:
if nums[l] != target: l += 1
if nums[r] != target: r -= 1
return [-1, -1]
class Solution {
fun getFirstPosition(nums: IntArray, target: Int): Int {
var l = 0
var r = nums.size - 1
while (l < r) {
val m = (l + r) / 2
if (target > nums[m]) l = m + 1
else r = m
}
return if (nums[l] == target) l else -1
}
fun getLastPosition(nums: IntArray, target: Int): Int {
var l = 0
var r = nums.size - 1
while (l < r) {
val m = (l + r + 1) / 2
if (target < nums[m]) r = m - 1
else l = m
}
return if (nums[l] == target) l else -1
}
fun searchRange(nums: IntArray, target: Int): IntArray {
if (nums.size == 0) return intArrayOf(-1, -1)
return intArrayOf(
getFirstPosition(nums, target),
getLastPosition(nums, target),
)
}
}Approach 2: Optimal Binary Search
To find the start and end indices, try to find the start index first, if it doesn't exist then the array not having the given element. So added a condition to check if the first index is not found then skip the end index block.
Instead of having two loops for both cases, have a flag that differentiates between the start and end index search space.
Time complexity:
Space complexity:
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
result[0] = searchIndex(nums, target, true);
if (result[0] != -1) {
result[1] = searchIndex(nums, target, false);
}
return result;
}
private int searchIndex(int[] nums, int target, boolean startIndex) {
int low = 0, high = nums.length - 1;
int index = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (target < nums[mid]) {
high = mid - 1;
} else if (target > nums[mid]) {
low = mid + 1;
} else {
index = mid;
if (startIndex) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return index;
}
}class Solution {
fun getFirstPosition(nums: IntArray, target: Int): Int {
var l = 0
var r = nums.size - 1
while (l < r) {
val m = (l + r) / 2
if (target > nums[m]) l = m + 1
else r = m
}
return if (nums[l] == target) l else -1
}
fun getLastPosition(nums: IntArray, target: Int): Int {
var l = 0
var r = nums.size - 1
while (l < r) {
val m = (l + r + 1) / 2
if (target < nums[m]) r = m - 1
else l = m
}
return if (nums[l] == target) l else -1
}
fun searchRange(nums: IntArray, target: Int): IntArray {
if (nums.size == 0) return intArrayOf(-1, -1)
val first = getFirstPosition(nums, target)
if (first == -1) return intArrayOf(-1, -1)
val last = getLastPosition(nums, target)
return intArrayOf(first, last)
}
}