Skip to main content

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

medium

Return the first and last index of a target in a sorted array with duplicates. The classic 'leftmost and rightmost' binary search drill — two passes, both in O(log n).

By Sam K., 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 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 = []
Output
[-1,-1]

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two binary searches: one for the leftmost occurrence, one for the rightmost.

Hint 2

Leftmost: same as 'lower_bound' — find the smallest index where nums[i] >= target.

Hint 3

Rightmost: find the largest index where nums[i] <= target — or equivalently lower_bound(target + 1) - 1.

Hint 4

After each search, validate that the returned index is in range and nums[idx] == target — otherwise return [-1, -1].

Solution approach

Reveal approach

Two passes of binary search. Helper leftBound(target): lo = 0, hi = n; while lo < hi: mid = lo + (hi - lo) / 2; if nums[mid] < target, lo = mid + 1; else hi = mid. Return lo — the smallest index where nums[idx] >= target. Call it once with target and once with target + 1. The result is [leftBound(target), leftBound(target + 1) - 1]. If the first call returns n (out of range) or nums[first] != target, the value isn't present — return [-1, -1]. O(log n) time, O(1) space. The lower_bound / upper_bound abstraction generalizes to dozens of binary-search-with-duplicates problems.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • lower-bound
  • upper-bound

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • LinkedIn

More Binary Search practice problems

See all Binary Search problems →