Skip to main content

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

mediumAsked at Reddit

Find 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 Alex Chen, 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^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. 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →