Minimum Window Sort (Shortest Unsorted Continuous Subarray)

• Find disorder boundaries – scan left for the first break, scan right for the last break.
• Compute window min/max – find the minimum and maximum within the candidate window.
• Extend boundaries – stretch left while outside elements exceed the window's min, stretch right while they are below the max.
• O(n) time, O(1) space – three linear scans with constant extra variables.
• Already sorted – if no break is found, the answer is 0.

What is the problem?

Given an array, find the length of the shortest contiguous subarray that, if sorted, would make the entire array sorted in ascending order. In a banking context, Rajesh maintains a tiered list of balances at National Bank of India that must be in ascending order, and a batch update shuffled a few values in the middle.

How does the two-pointer approach work?

Phase 1: Scan from the left to find the first index where arr[i] > arr[i+1], marking the left edge of the disorder. Scan from the right to find the last index where arr[i] < arr[i-1], marking the right edge.

Phase 2: Find the min and max within the candidate window [left, right]. Extend left while arr[left-1] > windowMin. Extend right while arr[right+1] < windowMax.

package com.bank.service;

public class MinWindowSort {

    public static int findUnsortedSubarray(int[] arr) {
        int n = arr.length;
        int left = 0, right = n - 1;

        // Phase 1: find rough boundaries
        while (left < n - 1 && arr[left] <= arr[left + 1]) left++;
        if (left == n - 1) return 0; // already sorted

        while (right > 0 && arr[right] >= arr[right - 1]) right--;

        // Phase 2: find min and max in candidate window
        int windowMin = Integer.MAX_VALUE;
        int windowMax = Integer.MIN_VALUE;
        for (int i = left; i <= right; i++) {
            windowMin = Math.min(windowMin, arr[i]);
            windowMax = Math.max(windowMax, arr[i]);
        }

        // Extend left while outside > windowMin
        while (left > 0 && arr[left - 1] > windowMin) left--;
        // Extend right while outside < windowMax
        while (right < n - 1 && arr[right + 1] < windowMax) right++;

        return right - left + 1;
    }

    public static void main(String[] args) {
        int[] balances = {1, 3, 2, 0, 5};
        int length = findUnsortedSubarray(balances);
        System.out.println("Minimum window to sort: " + length);
    }
}

Minimum window to sort: 4

Why is the extension step necessary?

The initial candidate window [left, right] marks where the order first and last breaks, but sorting only that window might leave values outside it stranded. For [1, 3, 2, 0, 5], the initial break points are indices 1 and 3, but the window's minimum is 0, which is smaller than arr[0] = 1, so the left boundary must extend to include index 0.

What about the already-sorted case?

If the left scan reaches the end without finding a break, the array is already sorted and the answer is 0.

What is the time and space complexity?

• Time: O(n) because each phase does at most one linear scan.
• Space: O(1) because only a constant number of variables are used.

How does this compare to the sort-and-compare approach?

The naive approach sorts a copy and compares with the original, finding the first and last differing positions. This is O(n log n) time and O(n) space. The two-pointer approach is O(n) time and O(1) space.

| Aspect | Sort and Compare | Two-Pointer |
|---|---|---|
| Time | O(n log n) | O(n) |
| Space | O(n) | O(1) |
| Correctness | Straightforward | Requires extension step |
| Code complexity | Simple | Moderate |

What are common mistakes?

The most common mistake is stopping at the initial break points without extending. Another is not handling the already-sorted case, which causes incorrect calculations when left reaches the end.

// Wrong: returning initial window without extension
return right - left + 1; // may be too narrow

// Correct: extend based on windowMin and windowMax first
while (left > 0 && arr[left - 1] > windowMin) left--;
while (right < n - 1 && arr[right + 1] < windowMax) right++;
return right - left + 1;

What are edge cases?

• Already sorted array: return 0.
• Entire array is unsorted (reversed): return n.
• Single element: return 0.
• Two elements out of order: return 2.

What should a senior engineer know?

A senior engineer explains why the initial break points alone are insufficient: the min or max within the disordered region may force the boundaries to expand. The senior also mentions that this problem can be solved in a single pass using a monotonic-stack approach, tracking the leftmost and rightmost positions that violate monotonicity.