Find First and Last Position in Sorted Array

MediumBinary Searchbinary search bounds

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array of integers nums sorted in non-decreasing order, along with a target value. Your task is to locate the **starting index** and the **ending index** of all occurrences of target within the array. Return the answer as a two-element array [first, last], where first is the smallest index whose value equals target and last is the largest such index. If target never appears in nums, return [-1, -1]. Your algorithm must run in O(log n) time, so a plain linear scan will not satisfy the intended complexity. The idea is to run two separate binary searches: one that hugs the left edge of the matching range and one that hugs the right edge.

Examples

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3, 4]
The value `8` first appears at index 3 and last appears at index 4.
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1, -1]
The value `6` is not present in the array, so both bounds are -1.
Input: nums = [], target = 0
Output: [-1, -1]
The array is empty, so the target cannot be found.

Constraints

  • `0 <= nums.length <= 10^5`
  • `-10^9 <= nums[i] <= 10^9`
  • `nums` is sorted in non-decreasing order
  • `-10^9 <= target <= 10^9`
  • The solution must run in `O(log n)` time

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.