Find First and Last Position of Element in Sorted Array Solution
Find First and Last Position of Element in Sorted Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find First and Last Position of Element in Sorted Array is a medium coding problem on arrays and binary search, asked in Amazon, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a nums sorted in non-decreasing order, return the first and last index of target as [first, last].
If target is absent, return [-1,-1]. The algorithm must run in O(log n) time.
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 = [1], target = 1
Output: [0,0]
Constraints
1 <= nums.length <= 100000-1000000000 <= nums[i], target <= 1000000000nums is sorted in non-decreasing order.
Hints for Find First and Last Position of Element in Sorted Array
Hint 1
Write one helper: the leftmost index where a value could be inserted (the lower bound).
Hint 2
The first occurrence is
lowerBound(target).Hint 3
The last occurrence is
lowerBound(target + 1) - 1.
How to solve Find First and Last Position of Element in Sorted Array
Both ends come from the same primitive. lowerBound(t) is the first index whose value is at least t; calling it twice pins the whole run of equal values without a second, mirror-image search.
Approach
- Implement
lowerBound(t): binary search over[0, n], movinglopastmidwhilenums[mid] < t. - Let
a = lowerBound(target). Ifa == nornums[a] != target, the value is absent. - Otherwise the answer is
[a, lowerBound(target + 1) - 1].
Why it works
nums[i] < t is false for a suffix of a sorted array, so the boundary is unique. lowerBound(target + 1) is the first index past every copy of target, so one less is the last copy. Using target + 1 rather than a separate upper-bound search halves the code, at the cost of assuming integer values — which the problem gives.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
target + 1can overflow whentargetis the maximum representable value; widen the type or write a true upper bound.- Checking
nums[a] != targetbefore thea == nguard reads out of bounds. - A linear scan after finding one occurrence is
O(n)and fails the required complexity.
Reference solution
Python
from typing import List
def searchRange(nums: List[int], target: int) -> List[int]:
def lower(t: int) -> int:
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < t:
lo = mid + 1
else:
hi = mid
return lo
a = lower(target)
if a == len(nums) or nums[a] != target:
return [-1, -1]
return [a, lower(target + 1) - 1]Java
private static int lowerBoundRange(int[] nums, long t) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] < t) lo = mid + 1; else hi = mid;
}
return lo;
}
public static int[] searchRange(int[] nums, int target) {
int a = lowerBoundRange(nums, target);
if (a == nums.length || nums[a] != target) return new int[] { -1, -1 };
return new int[] { a, lowerBoundRange(nums, (long) target + 1) - 1 };
}C++
static int lowerBoundRange(vector<int>& nums, long long t) {
int lo = 0, hi = (int) nums.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] < t) lo = mid + 1; else hi = mid;
}
return lo;
}
vector<int> searchRange(vector<int>& nums, int target) {
int a = lowerBoundRange(nums, target);
if (a == (int) nums.size() || nums[a] != target) return vector<int>{ -1, -1 };
return vector<int>{ a, lowerBoundRange(nums, (long long) target + 1) - 1 };
}JavaScript
var searchRange = function(nums, target) {
var lower = function(t) {
var lo = 0, hi = nums.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (nums[mid] < t) lo = mid + 1; else hi = mid;
}
return lo;
};
var a = lower(target);
if (a === nums.length || nums[a] !== target) return [-1, -1];
return [a, lower(target + 1) - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search