Skip to main content

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

mediumAsked at Vercel

Given a sorted array, find the first and last index of a target in O(log n). Vercel asks this for the two-binary-search pattern (lower-bound + upper-bound) — same shape as their time-range bucket lookup for analytics queries.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel screen; bound semantics expected.
  • Blind (2026-Q1)— Listed in Vercel platform onsite.

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]

Approaches

1. One binary search + expand both ways

Find any occurrence; linearly scan left and right.

Time
O(n) worst case
Space
O(1)
// O(n) in the all-duplicates case. Mention but pivot.

Tradeoff: Worst case O(n) when the target spans the whole array.

2. Two binary searches (lower-bound and upper-bound) (optimal)

First binary search finds the leftmost index >= target. Second finds the leftmost index > target; subtract 1 for last position.

Time
O(log n)
Space
O(1)
function searchRange(nums, target) {
  function 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 start = lower(target);
  if (start === nums.length || nums[start] !== target) return [-1, -1];
  const end = lower(target + 1) - 1;
  return [start, end];
}

Tradeoff: Two log n searches. The 'lower(target + 1) - 1' trick avoids writing a separate upper-bound function. Both passes use the same lower-bound primitive.

Vercel-specific tips

Vercel grades for the lower-bound + upper-bound abstraction. Bonus signal: writing ONE lower-bound function and calling it twice (with target and target+1) rather than two near-identical binary searches. Mention that this also generalizes to count occurrences (end - start + 1).

Common mistakes

  • Returning early on first match — finds an arbitrary index, not the first.
  • Implementing upper-bound from scratch with subtle inversion bugs — easier to call lower(target+1).
  • Forgetting the not-found check (nums[start] !== target).

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Count occurrences of target — end - start + 1.
  • Find the kth occurrence.
  • Search insert position (LC 35) — lower-bound directly.

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 calls to lower-bound?

Lower-bound returns the first index where nums[i] >= target. For the LAST position, we want the first index where nums[i] > target, then subtract 1. Both are 'find smallest index satisfying X' — the same primitive.

What if the target isn't present?

lower(target) returns either nums.length or an index where nums[i] > target. Check both — if either holds, return [-1, -1].

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →