Skip to main content

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

mediumAsked at Plaid

Find the first and last occurrence of a target in a sorted array. Plaid asks this because finding the time-range of all transactions for a given merchant in a sorted ledger is the same primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid backend OA — merchant range lookup.
  • LeetCode Discuss (2026)— Plaid binary-search variant.

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. Linear scan

Walk forward, then backward.

Time
O(n)
Space
O(1)
function searchRange(nums, target) {
  const first = nums.indexOf(target);
  if (first === -1) return [-1, -1];
  return [first, nums.lastIndexOf(target)];
}

Tradeoff: Misses the O(log n) requirement.

2. Two binary searches (lower bound + upper bound)

Lower bound finds the first index where nums[i] >= target. Upper bound finds the first index where nums[i] > target. Range is [lower, upper - 1].

Time
O(log n)
Space
O(1)
function searchRange(nums, target) {
  function lower() {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (nums[mid] < target) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
  function upper() {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (nums[mid] <= target) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
  const lo = lower();
  if (lo === nums.length || nums[lo] !== target) return [-1, -1];
  return [lo, upper() - 1];
}

Tradeoff: Two clean binary searches. The lower-bound + upper-bound pair is the standard way to find ranges in sorted arrays.

Plaid-specific tips

Plaid grades this on whether you reach for two separate lower/upper bound searches rather than one search followed by linear expansion. Bonus signal: connect to merchant-range queries — given a sorted ledger by merchant_id, find all rows for merchant X with two binary searches.

Common mistakes

  • Using a single binary search then linear-scanning outward — TLE on a long run of equal values.
  • Confusing lower bound (>=) with upper bound (>) — off by one on duplicates.
  • Forgetting to verify nums[lo] === target before returning the range.

Follow-up questions

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

  • Count occurrences (upper - lower).
  • Range queries on a 2D sorted matrix.
  • Merchant-window lookup in a sorted transaction ledger.

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 with expansion?

A long run of equal values makes the expansion O(n) in the worst case, defeating the O(log n) requirement.

Why use half-open [lo, hi) instead of closed [lo, hi]?

Lower-bound and upper-bound search are cleaner with half-open intervals. The terminating condition lo === hi gives the answer directly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →