Typical example
Input
arr = [2, 6, 4, 8, 10, 9, 15]
Output
5
Sorting the subarray from index 1 to 5 (6,4,8,10,9) makes the whole array sorted. The window length is 5.
Full lesson preview
Find the smallest window to sort an array
Return the length of the smallest subarray that, if sorted, makes the whole array sorted.
Python practice28 minTwo Pointers & Sliding WindowAdvancedLast updated March 26, 2026
Problem statement
Given an integer array arr, find the length of the smallest contiguous subarray such that sorting only that subarray results in the entire array being sorted in non-decreasing order. If the array is already sorted, return 0. Achieve O(n) time by scanning from both ends and then expanding the identified unsorted window based on its min and max values.
Task
Use linear passes and window expansion to determine the minimal subarray that must be sorted so the entire array becomes sorted.
Examples
Input format
A list of integers arr.
Output format
An integer representing the length of the smallest window to sort. Return 0 if already sorted.
Constraints
Do it in O(n) time and O(1) extra space if possible (ignoring input). Array length can be up to typical interview constraints (e.g., 10^5).
Samples
Sample 1
Input
arr = [1, 2, 3, 4, 5]
Output
0
Already sorted array requires no window.