medium Minimum Window Sort

Problem Statement

Given an array, find the length of the smallest subarray in it which when sorted will sort the whole array.

Example 1:

Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted

Example 2:

Input: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted

Example 3:

Input: [1, 2, 3]
Output: 0
Explanation: The array is already sorted

Example 4:

Input: [3, 2, 1]
Output: 3
Explanation: The whole array needs to be sorted.

Constraints:

1 <= arr.length <= 10⁴
-10⁵ <= arr[i] <= 10⁵

Try it yourself

Try solving this question here:

After you try — Pattern Transfer

Pattern: FIND MINIMUM UNSORTED SUBARRAY (two-boundary + extend by min/max of the candidate span).

CRITICAL: Despite the word “Window” in the title, this is NOT sliding window. Sliding window expands/shrinks a contiguous range under a running constraint (sum, unique count, …). Here you find boundaries of disorder then extend so that sorting that span sorts the whole array — a fixed structural repair, not a moving validity window.

When NOT: you need the array fully sorted as output → sort all O(n log n); you need min window substring of another string → real sliding window / two pointers on strings.

Edges

Already sorted: [1,2,3] → 0.
Fully reversed: [3,2,1] → 3.
Single: [1] → 0.

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Minimum Window Sort medium

Why this concept exists (judgment layer)

Despite 'Window' in the title, this is FIND MIN UNSORTED SUBARRAY: locate disorder boundaries then extend so sorting that span sorts the whole array. Confusing it with sliding window is a K12 failure mode the panel drills hard.

Worked example with complexity derivation

[1,2,5,3,7,10,9,12]:
Left pass: first dip candidate around 5>3 → low boundary near index 2.
Right pass: 10>9 → high boundary near 10,9.
Candidate span [5,3,7,10,9]; min=3,max=10. Extend left while arr[i]>min; right while arr[i]<max
so that after sort, left of span ≤ min and right ≥ max.
Length 5 (indices 2..6). Already sorted [1,2,3]→0; reverse [3,2,1]→3.
Time Θ(n) two/three linear passes; space Θ(1).

Pattern + when-NOT / named alternative

PATTERN: two-boundary scan + extend by min/max of candidate (NOT sliding window). WHEN NOT: need fully sorted output → sort all O(n log n). Min window substring of another string → real variable window with need-counts. Do not maintain a moving validity sum/set.

Edge case / failure mode

Edges: sorted → 0; single → 0; fully reversed → n; duplicates (extend carefully so equals stay valid). Failure: return first-descent to first-ascent without min/max extend — leaves array unsorted outside.

Hostile-panel drills (defend the decision)

Q1. Why is this not sliding window?
Model answer: No expand/shrink under a running constraint; one structural repair length for the array.

Q2. Why extend by min/max of the candidate?
Model answer: A value smaller than min to the left (or larger than max to the right) would be out of order after sorting only the candidate.

Q3. Complexity vs full sort?
Model answer: O(n) identify span vs O(n log n) sort everything — win when only a small middle is disordered.

✅ Solution Minimum Window Sort

Problem Statement

Given an array, find the length of the smallest subarray in it which when sorted will sort the whole array.

Example 1:

Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted

Example 2:

Input: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted

Example 3:

Input: [1, 2, 3]
Output: 0
Explanation: The array is already sorted

Example 4:

Input: [3, 2, 1]
Output: 3
Explanation: The whole array needs to be sorted.

Constraints:

1 <= arr.length <= 10⁴
-10⁵ <= arr[i] <= 10⁵

Solution

As we know, once an array is sorted (in ascending order), the smallest number is at the beginning and the largest number is at the end of the array. So if we start from the beginning of the array to find the first element which is out of sorting order i.e., which is smaller than its previous element, and similarly from the end of array to find the first element which is bigger than its previous element, will sorting the subarray between these two numbers result in the whole array being sorted?

Let’s try to understand this with Example-2 mentioned above. In the following array, what are the first numbers out of sorting order from the beginning and the end of the array:

    [1, 3, 2, 0, -1, 7, 10]

Starting from the beginning of the array the first number out of the sorting order is ‘2’ as it is smaller than its previous element which is ‘3’. Starting from the end of the array the first number out of the sorting order is ‘0’ as it is bigger than its previous element which is ‘-1’ As you can see, sorting the numbers between ‘3’ and ‘-1’ will not sort the whole array. To see this, the following will be our original array after the sorted subarray:

    [1, -1, 0, 2, 3, 7, 10]

The problem here is that the smallest number of our subarray is ‘-1’ which dictates that we need to include more numbers from the beginning of the array to make the whole array sorted. We will have a similar problem if the maximum of the subarray is bigger than some elements at the end of the array. To sort the whole array we need to include all such elements that are smaller than the biggest element of the subarray.

Step-by-step Algorithm

Initialize Pointers: Set low to 0 and high to the last index of the array.
Find Left Boundary:
- Move low to the right while the current element is less than or equal to the next element.
Check If Sorted:
- If low reaches the end, the array is already sorted. Return 0.
Find Right Boundary:
- Move high to the left while the current element is greater than or equal to the previous element.
Find Min and Max:
- Iterate from low to high to find the minimum and maximum values in this subarray.
Extend Left Boundary:
- Move low to the left while the previous element is greater than the subarray's minimum.
Extend Right Boundary:
- Move high to the right while the next element is less than the subarray's maximum.
Calculate Length:
- The length of the subarray to be sorted is high - low + 1.

Algorithm Walkthrough

Using the input [1, 3, 2, 0, -1, 7, 10]:

Initialize Pointers: low = 0, high = 6.
Find Left Boundary:
- Compare 1 and 3, move low to 1.
- Compare 3 and 2, stop. low = 1.
Find Right Boundary:
- Compare 10 and 7, move high to 5.
- Compare 7 and -1, move high to 4.
- Compare -1 and 0, stop at 4.
Find Min and Max:
- Subarray is [3, 2, 0, -1].
- Minimum is -1, Maximum is 3.
Extend Left Boundary:
- 1 is greater than -1, low decrements to 0.
Extend Right Boundary:
- 7 is not less than 3, high stays 4.
Calculate Length:
- Length is high - low + 1 = 4 - 0 + 1 = 5.

Here is the visual representation of this algorithm for Example 1:

Code

Here is what our algorithm will look like:

java

class Solution {

  public int sort(int[] arr) {
    int low = 0, high = arr.length - 1;
    // find the first number out of sorting order from the beginning
    while (low < arr.length - 1 && arr[low] <= arr[low + 1]) low++;

    if (
      low == arr.length - 1
    ) return 0; // if the array is sorted

    // find the first number out of sorting order from the end
    while (high > 0 && arr[high] >= arr[high - 1]) high--;

    // find the maximum and minimum of the subarray
    int subarrayMax = Integer.MIN_VALUE, subarrayMin = Integer.MAX_VALUE;
    for (int k = low; k <= high; k++) {
      subarrayMax = Math.max(subarrayMax, arr[k]);
      subarrayMin = Math.min(subarrayMin, arr[k]);
    }

    // extend the subarray to include any number which is bigger than the minimum of
    // the subarray
    while (low > 0 && arr[low - 1] > subarrayMin) low--;
    // extend the subarray to include any number which is smaller than the maximum of
    // the subarray
    while (high < arr.length - 1 && arr[high + 1] < subarrayMax) high++;

    return high - low + 1;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.sort(new int[] { 1, 2, 5, 3, 7, 10, 9, 12 }));
    System.out.println(sol.sort(new int[] { 1, 3, 2, 0, -1, 7, 10 }));
    System.out.println(sol.sort(new int[] { 1, 2, 3 }));
    System.out.println(sol.sort(new int[] { 3, 2, 1 }));
  }
}

Complexity Analysis

Time Complexity

First and second while loops (finding low and high): The first two while loops each scan a portion of the array once to identify the first and last indices (low and high) where the array is out of order. Both loops run in time, where N is the length of the array.
Subarray max and min calculation: The for loop that finds the maximum and minimum values within the subarray between low and high runs at most because it scans the array between low and high. In the worst case, this could be the entire array.
Third and fourth while loops (extending the subarray): These loops extend the subarray by comparing the elements outside the subarray with the subarrayMin and subarrayMax. Both of these loops run in time because they only scan the array once.

Overall time complexity: Each operation is , so the overall time complexity of the algorithm is .

Space Complexity

Constant space: The algorithm uses only a few variables (low, high, subarrayMax, subarrayMin, etc.), all of which require constant space, .
In-place modification: The algorithm does not use any additional data structures that scale with the input size, and it processes the array in place.

Overall space complexity: , since only a constant amount of extra space is used.

Pattern Transfer — FIND MINIMUM UNSORTED SUBARRAY (boundary + extend)

Pattern name: minimum unsorted subarray (two-boundary + extend by subarray min/max).

Template:

From left, find first index where order breaks (not non-decreasing).
From right, find first break of non-increasing scan from the end.
Let candidate be that span; compute its min and max.
Extend left while a[low−1] > subMin; extend right while a[high+1] < subMax.
Return high − low + 1, or 0 if already sorted.

Recognition: shortest subarray that, if sorted, makes the whole array sorted.

NOT sliding window: no two pointers expand/shrink on a running validity constraint (sum/frequency). The word “window” here only means “span of indices.” Do not reach for SW templates.

When NOT: need the sorted array itself → full sort O(n log n); different problem “min window substring” → SW.

Complexity: a few linear passes → Θ(n) time, O(1) space.

Why extend (already taught well on page): sorting only the first descent-to-ascent span can leave smaller elements that belong further left — extend so every element outside the span is already in final sorted position relative to the span’s min/max.

Edge hand-runs

Sorted [1,2,3]: left scan reaches end → return 0.
Reverse [3,2,1] → length 3 (entire array).
Duplicates: use non-strict comparisons carefully (≤/≥ in boundary scans) so equal runs do not false-trigger; e.g. [1,2,2,1] must extend to cover the final 1.
Single element → 0.
Main: [1,3,2,0,-1,7,10] → after extend length 5; sorting that span sorts the array.

Drill: In one sentence, contrast this pattern with variable sliding window for “longest subarray with sum ≤ k.”

🧩 Pattern · Two Pointers

Recognize it: A sorted array where you need a pair/triplet or an in-place partition → walk two indices inward.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Minimum Window Sort? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Minimum Window Sort** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Minimum Window Sort** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Minimum Window Sort**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Minimum Window Sort**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Comparing Strings containing Backs