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 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 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

Practice these live with InterviewChamp.AI

Drill Find First and Last Position of Element in Sorted Array and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →