Given an array, find the length of the smallest subarray that, when sorted, results in the entire array being sorted.
📥 Examples Example 1 Input: [1, 3, 2, 0, -1, 7, 10] Output: 5 Explanation: The subarray [3, 2, 0, -1, 7] must be sorted to sort the entire array.
Example 2 Input: [1, 2, 5, 3, 7, 10, 9, 12] Output: 5 Explanation: The subarray [5, 3, 7, 10, 9] must be sorted.
💡 Approach: Sliding Window Strategy We need to:
Find the first element out of order from the start.
Find the first element out of order from the end.
Determine the minimum and maximum of the subarray between them.
Expand the window left/right if the min/max affect the elements outside.
Return the length of this window.
🧠 Java Code java Copy Edit public int shortestWindowToSort(int[] arr) { int low = 0, high = arr.length - 1;
// Step 1: Move 'low' forward while array is sorted
while (low < arr.length - 1 && arr[low] <= arr[low + 1]) {
low++;
}
// Array is already sorted
if (low == arr.length - 1) return 0;
// Step 2: Move 'high' backward while array is sorted
while (high > 0 && arr[high] >= arr[high - 1]) {
high--;
}
// Step 3: Find min and max in the subarray
int subarrayMin = Integer.MAX_VALUE;
int subarrayMax = Integer.MIN_VALUE;
for (int k = low; k <= high; k++) {
subarrayMin = Math.min(subarrayMin, arr[k]);
subarrayMax = Math.max(subarrayMax, arr[k]);
}
// Step 4: Expand window to the left
while (low > 0 && arr[low - 1] > subarrayMin) {
low--;
}
// Step 5: Expand window to the right
while (high < arr.length - 1 && arr[high + 1] < subarrayMax) {
high++;
}
return high - low + 1;
} ⏱ Time Complexity O(N) — Only a few linear scans through the array.
💾 Space Complexity O(1) — Constant space, no extra data structures used.
✅ Summary We don’t sort the array; we find the part that needs sorting.
Expand the range if sorting the subarray still doesn’t fix the full array.
Efficient and clean solution — great for interviews and real-world use.