Find first and last occurrence in sorted array
Company: Applied
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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]`
Quick Answer: 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.
Return the first and last index of target in a sorted array, or [-1, -1].
Constraints
- nums is sorted non-decreasing
Examples
Input: ([5, 7, 7, 8, 8, 10], 8)
Expected Output: [3, 4]
Explanation: Prompt example.
Input: ([1, 2, 3], 4)
Expected Output: [-1, -1]
Explanation: Absent target.
Input: ([], 0)
Expected Output: [-1, -1]
Explanation: Empty array.
Input: ([2, 2, 2], 2)
Expected Output: [0, 2]
Explanation: All values match.
Hints
- Use lower and upper bounds.