42. Find First and Last Position of Element in Sorted Array
mediumAsked at OlaFind the start and end indices of a target in a sorted array in O(log n).
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
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, return [-1, -1]. Must run in O(log n).
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums is sorted non-decreasing
Examples
Example 1
Input
nums = [5,7,7,8,8,10], target = 8Output
[3,4]Example 2
Input
nums = [5,7,7,8,8,10], target = 6Output
[-1,-1]Approaches
1. Linear scan
Sweep once for first match, once for last match.
- Time
- O(n)
- Space
- O(1)
const a = nums.indexOf(target), b = nums.lastIndexOf(target);
return [a, b];Tradeoff:
2. Two binary searches
Search the leftmost and rightmost insertion points; if the leftmost value isn't target, return [-1, -1].
- Time
- O(log n)
- Space
- O(1)
function searchRange(nums, target) {
const lower = t => {
let lo = 0, hi = nums.length;
while (lo < hi) { const m = (lo+hi)>>1; if (nums[m] < t) lo = m+1; else hi = m; }
return lo;
};
const a = lower(target), b = lower(target + 1) - 1;
if (a === nums.length || nums[a] !== target) return [-1, -1];
return [a, b];
}Tradeoff:
Ola-specific tips
Ola uses this to test boundary binary-search; tie it to finding the start and end of a surge-band index in a sorted multiplier table.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.