Smallest re-edit span: hints, no solution
Medium · Two pointers
A playlist is stored as a list of track numbers, and the producer wants the running order to be non-decreasing. They will pick one contiguous section of the playlist and re-edit it by sorting only that section, leaving everything else where it is.
Return the length of the shortest section that can be sorted so that the whole playlist becomes non-decreasing. If the playlist is already non-decreasing, return 0. Track numbers may repeat, and equal numbers next to each other are in a valid order.
Examples
- Input
- tracks = [2, 9, 4, 6, 5, 11]
- Output
- 4
- Note
- Sorting positions 1 to 4, which hold 9, 4, 6, 5, fixes the whole list.
- Input
- tracks = [1, 2, 2, 3]
- Output
- 0
- Note
- The list is already in order, so no section needs editing.
- Input
- tracks = [4, 3, 2, 1]
- Output
- 4
- Note
- The whole list is reversed, so the section is the whole list.
Constraints
- 0 <= tracks.length <= 250000
- 1 <= tracks[i] <= 100000
- Return 0 if already non-decreasing
Hint 1: a nudge
Where must the section begin and end at the very least, if you look only at the first and last places where order breaks?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.