Skip to main content

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

mediumAsked at Workday

Given a sorted array and a target, find the first and last index of the target. Workday uses this to test binary-search variants — same pattern as finding the first and last shift assigned to an employee within a sorted timeline.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 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. Linear scan

Walk and remember first and last index of target.

Time
O(n)
Space
O(1)
// violates O(log n) requirement

Tradeoff: Doesn't meet the constraint.

2. Two binary searches: lower and upper bound

First search finds leftmost occurrence. Second finds rightmost (or use lower bound of target+1, then subtract).

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 l = lowerBound(target);
  const r = lowerBound(target + 1) - 1;
  if (l <= r && nums[l] === target) return [l, r];
  return [-1, -1];
}

Tradeoff: Two clean binary searches. Using lowerBound(t+1) - 1 avoids writing a second 'upper bound' variant.

Workday-specific tips

Workday grades for code reuse — using one lower-bound function twice is cleaner than writing two parallel binary searches. Discuss the integer overflow potential of target+1 for INT_MAX targets (handled by JS but worth mentioning in Java/C++).

Common mistakes

  • Implementing two different binary searches (lower and upper) — twice the bug surface.
  • Forgetting the existence check at the end (l <= r && nums[l] === target).
  • Off-by-one in upper bound — using lowerBound(t+1) without subtracting 1.

Follow-up questions

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

  • Search Insert Position (LC 35) — only need the lower bound.
  • Count number of occurrences — r - l + 1.
  • What if duplicates can be huge?

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 lowerBound(target + 1) - 1?

lowerBound(x) returns the first index where nums[i] >= x. lowerBound(target+1) returns the first index past the target's range. Subtracting 1 gives the last index of target.

What if target overflow (target == INT_MAX)?

In JS, target+1 is safe up to 2^53. In Java/C++ you'd use a separate upper-bound function or check for overflow.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →