Medium

Find First and Last Position of Element in Sorted Array

LAB

Given sorted nums and target, return the first and last target index, or [-1, -1] if missing.

EXAMPLES

Example 1

Input
{
  "nums": [
    5,
    7,
    7,
    8,
    8,
    10
  ],
  "target": 8
}

Output
[
  3,
  4
]

FUNCTION SHAPE

nums: intArraytarget: int→intArray

SOLUTION NOTE

Run both min and max templates. Min gives leftmost, max gives rightmost.

Reveal reference solution +

pythonREFERENCE

def searchRange(self, nums: List[int], target: int) -> List[int]:
    if not nums:
        return [-1, -1]

    # Find leftmost (min template)
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid
        else:
            left = mid + 1
    if nums[left] != target:
        return [-1, -1]
    first = left

    # Find rightmost (max template)
    left, right = 0, len(nums) - 1
    while left < right:
        mid = ceil(left + (right - left) / 2)
        if nums[mid] <= target:
            left = mid
        else:
            right = mid - 1
    return [first, left]

TimeO(log n)

SpaceO(1)

Open on LeetCode ↗