Find first and last index of target
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an integer array `nums` sorted in non-decreasing order and an integer `target`.
Return a pair `[left, right]` where:
- `left` is the index of the first occurrence of `target` in `nums`
- `right` is the index of the last occurrence of `target` in `nums`
If `target` does not exist in the array, return `[-1, -1]`.
## Requirements
- Your algorithm must run in **O(log n)** time.
## Input/Output
- **Input:** `nums: int[]`, `target: int`
- **Output:** `int[2]` representing `[left, right]`
## Constraints
- `0 <= nums.length <= 1e5`
- `-1e9 <= nums[i], target <= 1e9`
- `nums` is sorted in non-decreasing order.
## Examples
- `nums = [5,7,7,8,8,10]`, `target = 8` → `[3,4]`
- `nums = [5,7,7,8,8,10]`, `target = 6` → `[-1,-1]`
- `nums = []`, `target = 0` → `[-1,-1]`
Quick Answer: This question evaluates mastery of searching algorithms and algorithmic complexity analysis, particularly the ability to locate boundary positions within a sorted array.
Return the first and last index of target in a sorted array, or [-1, -1] if absent.
Constraints
- nums is sorted non-decreasing
Examples
Input: ([5, 7, 7, 8, 8, 10], 8)
Expected Output: [3, 4]
Explanation: Prompt example.
Input: ([5, 7, 7, 8, 8, 10], 6)
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_bound and upper_bound.