Find first and last occurrence in sorted array

Q: Find first and last occurrence in sorted array

This question evaluates proficiency in array search algorithms and algorithmic reasoning, specifically the use of binary search techniques and careful boundary/edge-case handling to identify first and last occurrences.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given an array of integers nums sorted in non-decreasing order and an integer target.

Return a pair of indices [first, last] such that:

first is the smallest index i with nums[i] == target
last is the largest index j with nums[j] == target

If target does not exist in the array, return [-1, -1].

Requirements

Aim for an algorithm better than linear time (i.e., use binary search style reasoning).

Input / Output

Input: nums: int[] , target: int
Output: int[2] representing [first, last]

Constraints (typical)

0 <= nums.length <= 10^5
nums is sorted in non-decreasing order
Values fit in 32-bit signed integers

Example

nums = [5,7,7,8,8,10] , target = 8 → [3,4]
nums = [1,2,3] , target = 4 → [-1,-1]