We have an array that might be almost sorted, meaning most of it is in order but some middle section is out of place. The task is to find the smallest window that, if we sorted only that part, the entire array would become sorted.

The complication is that the unsorted section is not always the obvious one. A single misplaced element can extend the unsorted window further than its own position. Consider [1, 3, 2, 2, 2]: the 3 at index 1 is the only value that looks wrong, but the window has to stretch all the way to index 4, because every 2 after the 3 is smaller than it and would move during a sort.

The unsorted subarray is bounded by two positions. On the left, the first position holding an element greater than something that comes after it. On the right, the last position holding an element smaller than something that came before it. The work is finding these two boundaries efficiently.

Key Constraints:

Intuition

If we know what the fully sorted array looks like, we can compare it to the original element by element. The first position where the two differ is the left boundary of the unsorted subarray, and the last position where they differ is the right boundary.

This works because every element outside the unsorted window already sits in its correct sorted position, so it matches the sorted copy. The elements inside the window are exactly the ones that would move during a full sort, so they are the ones that differ.

Algorithm

Visualization and Code

The full sorted order is more than we need. The next approach finds the same two boundaries directly, in linear time and constant extra space, by detecting where elements sit lower or higher than their neighbors require.

Intuition

In a fully sorted array, each element is at least as large as everything before it and at most as large as everything after it. We can find the unsorted boundaries by checking where this fails.

Scanning left to right, track the maximum seen so far. Any element smaller than that running maximum is out of place: a larger value already appeared earlier, so this element would have to move left during a sort. The rightmost such element is the right edge of the unsorted window. Everything past it is larger than the entire prefix, so it never moves.

Scanning right to left, track the minimum seen so far. Any element larger than that running minimum is out of place, because a smaller value appears later and this element would move right. The leftmost such element is the left edge of the window.

This captures the window's full extent even when the source of the disorder sits at one end. In [1, 3, 2, 2, 2], the running maximum becomes 3 at index 1, and every later 2 is smaller than 3, so each one is flagged and the right edge extends to index 4.

Algorithm

Visualization and Code