42. Find First and Last Position of Element in Sorted Array
mediumAsked at RedditFind the first and last index of a target in a sorted array. Reddit asks this to test bound-based binary search — the same shape used when querying their time-bucketed vote logs for the range of events matching a timestamp.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Reddit loops.
- Glassdoor (2026-Q1)— Reddit data-team phone screen.
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 in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums is a non-decreasing array.-10^9 <= target <= 10^9
Examples
Example 1
nums = [5,7,7,8,8,10], target = 8[3,4]Example 2
nums = [5,7,7,8,8,10], target = 6[-1,-1]Example 3
nums = [], target = 0[-1,-1]Approaches
1. Find one then linear-scan both directions
Standard binary search to find any occurrence; expand left and right.
- Time
- O(log n + k) where k = match count
- Space
- O(1)
function searchRange(nums, target) {
let lo = 0, hi = nums.length - 1, found = -1;
while (lo <= hi) {
const mid = (lo + hi) >>> 1;
if (nums[mid] === target) { found = mid; break; }
if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
if (found === -1) return [-1, -1];
let l = found, r = found;
while (l > 0 && nums[l - 1] === target) l--;
while (r < nums.length - 1 && nums[r + 1] === target) r++;
return [l, r];
}Tradeoff: Degrades to O(n) when target spans the whole array ([1,1,1,...,1]).
2. Two binary searches: lower and upper bound (optimal)
First binary search finds the leftmost target; second finds the leftmost > target. Range = [first, second - 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 mid = (lo + hi) >>> 1;
if (nums[mid] < t) lo = mid + 1;
else hi = mid;
}
return lo;
};
const l = lower(target);
if (l === nums.length || nums[l] !== target) return [-1, -1];
return [l, lower(target + 1) - 1];
}Tradeoff: Pure O(log n). Reusing lower_bound for both ends is canonical.
Reddit-specific tips
Reddit interviewers grade on whether you reach for lower_bound + upper_bound rather than 'find any + expand'. Bonus signal: connect to range queries on their time-bucketed vote logs.
Common mistakes
- Falling into the expand-from-middle trap (O(n) worst case).
- Off-by-one on hi (use nums.length, not nums.length - 1, for lower_bound).
- Forgetting the 'not found' guard before computing the second bound.
Follow-up questions
An interviewer at Reddit may pivot to one of these next:
- Search insert position (LC 35).
- Find peak element (LC 162).
- Count occurrences of a target.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why lower(target + 1) instead of writing an upper_bound?
Mathematically equivalent for integer targets. Reuse simplifies code.
What about ties or sparse arrays?
Same approach. The 'not found' guard catches sparse cases.