Shortest window that sorts the whole array

Question

Given an array, find the length of the shortest contiguous subarray such that sorting just that subarray makes the whole array sorted ascending. If the array is already sorted, the answer is 0. Return the length of that shortest window. Aim for O(n) time and O(1) space.

Accepted Answer

An element is in the wrong place if some larger value sits to its left (it is below the running max from the left) or some smaller value sits to its right (it is above the running min from the right). The window that must be sorted stretches from the leftmost such offender to the rightmost. Find both with a forward scan tracking the max and a backward scan tracking the min. Tracing [2,6,4,8,10,9,15]: the forward scan flags 4 (index 2) and 9 (index 5) as below the running max, so right = 5. The backward scan flags 10 (index 4) and 6 (index 1) as above the running min, so left = 1. The window i…

Shortest window that sorts the whole array

Your answer

More Coding questions