Find the First and Last Target Positions with Binary Search
Company: Instacart
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a nondecreasing integer array and a target, return the zero-based indices of its first and last occurrence. Return [-1,-1] when the target is absent. Achieve O(log n) time.
### Constraints and Clarifications
The report explicitly identifies problem 34. The [official reference](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/) supplies the practice bounds: 0 <= n <= 100000; array values and target lie between -1000000000 and 1000000000. These are reference-context details, not separately reported interview bounds. Repeated values and an empty array are allowed.
### Example
For [1,2,2,2,5] and target 2, return [1,3]. For target 4, return [-1,-1].
### What a Strong Answer Covers
Use boundary searches rather than finding an arbitrary match and scanning duplicates. Explain interval invariants, absent-target handling, and the inclusive output endpoints.
### Follow-up Questions
- Why can a linear scan from one found occurrence violate the required complexity?
- How can the upper boundary be found without adding one to the target?
Overview: Locate the inclusive range of a target in a sorted array with two binary searches. Handle empty arrays, absent targets, and long duplicate runs while preserving logarithmic runtime.
Read the full Instacart Machine Learning Engineer interview experience this question came from
Given a nondecreasing integer array nums and an integer target, return [first, last], the zero-based indices of the first and last occurrence of target. Return [-1,-1] if target is absent. Use O(log n) time, including when nums is empty. For example, nums=[1,2,2,2,5] and target=2 returns [1,3], while target=4 returns [-1,-1].
Constraints
- nums is nondecreasing and may be empty.
- 0 <= nums.length <= 100000.
- Each array value and target is between -1000000000 and 1000000000, inclusive.
- Return zero-based inclusive endpoints or [-1,-1] when absent.
Examples
Input: ([1, 2, 2, 2, 5], 2)
Expected Output: [1, 3]
Explanation: The published repeated-target example.
Input: ([1, 2, 2, 2, 5], 4)
Expected Output: [-1, -1]
Explanation: The published absent-target example.
Hints
- Search for the first element that is at least target.
- The upper boundary can be found by comparing with target directly.