Skip to main content

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

mediumAsked at Datadog

Find the first and last index of a target in a sorted array using O(log n). Datadog asks this because their TSDB needs range-bisect (start and end of a value range) for every query that filters by timestamp.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog backend onsite — directly mapped to TSDB range queries.
  • Blind (2025-10)— Recurring at Datadog.

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

Binary search for one match, then expand left/right.

Time
O(log n + k)
Space
O(1)
function searchRange(nums, target) {
  let i = -1;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] === target) { i = mid; break; }
    if (nums[mid] < target) lo = mid + 1; else hi = mid - 1;
  }
  if (i === -1) return [-1, -1];
  let l = i, r = i;
  while (l > 0 && nums[l - 1] === target) l--;
  while (r < nums.length - 1 && nums[r + 1] === target) r++;
  return [l, r];
}

Tradeoff: O(log n + k) — degrades to O(n) when target appears many times. Doesn't meet the strict O(log n) requirement.

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

Run leftmost-binary-search (find first >= target) and rightmost-binary-search (find last <= target).

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

Tradeoff: Two binary searches, strict O(log n). The lower-bound / upper-bound idiom is the Datadog-canonical pattern for range queries in their TSDB.

Datadog-specific tips

Datadog interviewers expect the lower-bound / upper-bound idiom (the same as C++ STL). Articulate the half-open invariant [lo, hi) and explain WHY the comparison flips between leftBound (<) and rightBound (<=). This is foundational for range queries.

Common mistakes

  • Using one binary search + expansion — fails the strict O(log n) requirement when target is dense.
  • Mixing closed [lo, hi] and half-open [lo, hi) intervals in one function — bugs.
  • Forgetting the target-not-present check after leftBound — nums[l] might not equal target.

Follow-up questions

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

  • Find K Closest Elements (LC 658) — uses lower-bound as a building block.
  • Count Occurrences of a Number — rightBound - leftBound + 1.
  • Datadog-style: range-bisect for timestamps in TSDB block.

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 passes instead of one?

The leftmost and rightmost matches require different invariants. Combining them into one pass is possible but harder to get right — most teams (including Datadog) accept two clean binary searches.

Why the lo - 1 at the end of rightBound?

rightBound returns the first index > target. The last index == target is one before that, hence lo - 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →