Eastbound Survey Cleanup
Indices of the shortest subarray to remove to make an array nondecreasing
A wildlife team is tracking a herd moving east along a survey corridor. Each reading records the herd's signed eastward position relative to a fixed marker. Negative positions are west of the marker.
The readings are stored in observation order in positions. A consistent record has nondecreasing positions: each reading is at least the previous one. Equal positions are allowed.
The team may discard one contiguous block of readings. The readings outside that block stay in their original order.
Return [start, end], the inclusive, zero-based indices of the shortest block whose removal makes the remaining record nondecreasing. If several shortest blocks work, return the one with the smallest start.
If the record is already nondecreasing, return [-1, -1] to indicate that nothing should be removed. A record with zero or one remaining reading is considered nondecreasing.
Examples
Example 1
Input: positions = [1,3,8,2,4,6] Output: [1,2]
Removing the readings at indices 2 through 3 leaves [1, 3, 4, 6], which is nondecreasing. No single-reading removal works.
Example 2
Input: positions = [2,1,2] Output: [0,0]
Removing either of the first two readings makes the record nondecreasing. Both choices remove one reading, so the earlier block is selected.
Example 3
Input: positions = [-4,-4,0,3,3] Output: [-1,-1]
Repeated positions are allowed, and the entire record is already nondecreasing, so no readings need to be discarded.
Constraints
- 1 <= positions.length <= 8000
- -1000000 <= positions[i] <= 1000000
- All positions are integers.
Use inclusive indices for the removed block. Equal adjacent values are valid. The tie-break rule applies only when a nonempty block must be removed.
Hints
Show hint 1Hint 1
Identify the longest nondecreasing prefix and the longest nondecreasing suffix. Any retained readings on either side of a removed block must belong to these regions.
Show hint 2Hint 2
As you move the retained prefix endpoint to the right, the earliest compatible suffix endpoint can only move to the right as well.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return all shortest removable blocks, in increasing order of their start indices?
- How would the algorithm change if the remaining positions had to be strictly increasing?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem