CodePark/ problems / First and Last Position of a Value
START PRACTICINGPRACTICE
Coding problem · Data structures and algorithms › Binary search

First and Last Position of a Value

mediumabout 20 minutes in an interview

You get an array of integers nums, sorted in ascending order, and an integer target. The array may contain duplicates. Return [first, last]: the index of the first and the last occurrence of target.

  • If target is not in the array, return [-1, -1].
  • If it appears once, first and last are the same index.
  • nums can be empty, and it can hold up to 1,000,000 numbers.
  • A value may repeat hundreds of thousands of times. Even then, your solution must run in O(log n) time.
Input: nums = [1, 3, 3, 3, 5, 8], target = 3 Output: [1, 3]
Input: nums = [1, 3, 3, 3, 5, 8], target = 4 Output: [-1, -1]
Input: nums = [2, 2], target = 2 Output: [0, 1]