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