Coding questions · TikTok

Find first and last index of target

This question evaluates mastery of searching algorithms and algorithmic complexity analysis, particularly the ability to locate boundary positions within a sorted array.

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]

First and Last Index of Target

Hints

Use lower_bound and upper_bound.