Skip to main content

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

mediumAsked at Ola

Find the start and end indices of a target in a sorted array in O(log n).

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

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, return [-1, -1]. Must run in O(log n).

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is sorted non-decreasing

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

Sweep once for first match, once for last match.

Time
O(n)
Space
O(1)
const a = nums.indexOf(target), b = nums.lastIndexOf(target);
return [a, b];

Tradeoff:

2. Two binary searches

Search the leftmost and rightmost insertion points; if the leftmost value isn't target, return [-1, -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 m = (lo+hi)>>1; if (nums[m] < t) lo = m+1; else hi = m; }
    return lo;
  };
  const a = lower(target), b = lower(target + 1) - 1;
  if (a === nums.length || nums[a] !== target) return [-1, -1];
  return [a, b];
}

Tradeoff:

Ola-specific tips

Ola uses this to test boundary binary-search; tie it to finding the start and end of a surge-band index in a sorted multiplier table.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →