42. Find First and Last Position of Element in Sorted Array
mediumAsked at SnowflakeFind the first and last index of a target in a sorted array. Snowflake asks this to test lower_bound/upper_bound mechanics — the same primitive used to extract row ranges for a clustered-column predicate inside a micro-partition.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Snowflake loops.
- Glassdoor (2026-Q1)— Snowflake storage team uses this to set up range-predicate follow-up.
- LeetCode Discuss (2025-11)— Recurring at Snowflake new-grad onsites.
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. Binary search to any, then linear expand
Find any occurrence with binary search, then walk left and right linearly.
- Time
- O(log n + k)
- Space
- O(1)
function searchRange(nums, target) {
// standard binary search omitted for brevity
// then linear expand left and right
return [-1, -1]; // outline only
}Tradeoff: Worst case O(n) when k is large. Don't ship.
2. Two binary searches (lower / upper bound) (optimal)
First finds leftmost index where nums[i] >= target. Second finds leftmost index where nums[i] > target, then subtract one.
- Time
- O(log n)
- Space
- O(1)
function searchRange(nums, target) {
function lowerBound(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 start = lowerBound(target);
if (start === nums.length || nums[start] !== target) return [-1, -1];
return [start, lowerBound(target + 1) - 1];
}Tradeoff: Two binary searches, O(log n). The lower_bound abstraction is reusable across other range-predicate problems.
Snowflake-specific tips
Snowflake interviewers want the lower_bound abstraction — it's the right primitive and reusable. Bonus signal: pivot to micro-partition range scans — when Snowflake evaluates WHERE col BETWEEN a AND b, it binary-searches partitioned block-min-max metadata for the first overlapping block and the last, then streams blocks in between.
Common mistakes
- Computing the upper bound directly with > and getting an off-by-one on equality.
- Returning [-1, -1] without first verifying the lower bound landed on an equal element.
- Using strict closed intervals [lo, hi] instead of half-open [lo, hi) — leads to off-by-one bugs around target+1.
Follow-up questions
An interviewer at Snowflake may pivot to one of these next:
- Number of Occurrences of target in nums (LC 1351).
- How does Snowflake prune blocks for BETWEEN predicates?
- Find K Closest Elements (LC 658).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why two binary searches and not one extended?
Two clean lower_bound calls are easier to reason about. One extended search that returns both ends is doable but error-prone.
How does this connect to range predicates?
WHERE col BETWEEN a AND b is two lower_bound queries against the sorted column metadata: 'first block >= a' and 'first block > b'. The blocks in between are the candidate set.