Skip to main content

42. Find First and Last Position of Element in Sorted Array

mediumAsked at Snowflake

Find 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 Alex Chen, 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^9
  • nums is a non-decreasing array.
  • -10^9 <= target <= 10^9

Examples

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]

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Find First and Last Position of Element in Sorted Array and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →