Skip to main content
Talentd

Smallest Subarray to Sort in Every Sliding Window - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersStackGreedy10 min read
Practice this problem

Problem Statement

You are given an integer array nums and an integer k.

For each contiguous subarray of length k, determine the minimum length of a continuous segment that must be sorted so that the entire window becomes non‑decreasing; if the window is already sorted, its required length is zero.

Return an array of length n − k + 1 where each element corresponds to the answer for its window.

 

Example 1:

Input: nums = [1,3,2,4,5], k = 3

Output: [2,2,0]

Explanation:

  • nums[0...2] = [1, 3, 2]. Sort [3, 2] to get [1, 2, 3], the answer is 2.
  • nums[1...3] = [3, 2, 4]. Sort [3, 2] to get [2, 3, 4], the answer is 2.
  • nums[2...4] = [2, 4, 5] is already sorted, so the answer is 0.

Example 2:

Input: nums = [5,4,3,2,1], k = 4

Output: [4,4]

Explanation:

  • nums[0...3] = [5, 4, 3, 2]. The whole subarray must be sorted, so the answer is 4.
  • nums[1...4] = [4, 3, 2, 1]. The whole subarray must be sorted, so the answer is 4.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= k <= nums.length
  • 1 <= nums[i] <= 106

Approach Overview

Problem Overview: You are given an array and a sliding window. For each window, determine the smallest subarray that must be sorted so the entire window becomes sorted. The challenge is detecting the minimal unsorted region efficiently without repeatedly sorting every window.

Approach 1: Brute Force Window Check (Sorting Each Window) (Time: O(n * k log k), Space: O(k))

Iterate through every sliding window of size k. For each window, copy the elements and sort them using a standard sorting algorithm. Compare the sorted version with the original window to find the first and last indices where values differ. That range represents the smallest subarray that must be sorted. This approach is straightforward and useful for understanding the problem constraints, but repeatedly sorting each window is expensive and becomes slow for large arrays.

Approach 2: Monotonic Stack Boundary Detection (Time: O(n), Space: O(n))

A common technique for identifying unsorted regions uses a monotonic stack. Scan from left to right and maintain a stack of increasing elements. When a smaller element appears, it breaks the sorted order and indicates that earlier elements belong in the unsorted region. Repeat from the right side with a decreasing stack to determine the right boundary. The stack helps detect disorder efficiently without sorting. While powerful, managing stack state across sliding windows can add implementation complexity.

Approach 3: Enumeration with Left Maximum and Right Minimum (Time: O(n), Space: O(n))

This approach relies on tracking violations of sorted order using prefix and suffix information. While iterating through the array, maintain the maximum value seen from the left. If the current element is smaller than this left maximum, it must belong to the unsorted region. Similarly, track the minimum value from the right to detect elements that are larger than a future value. These two passes identify the minimal boundaries that need sorting. The method works because any element smaller than a previous maximum or larger than a later minimum breaks sorted order. The logic uses simple array scans and fits naturally with array processing patterns.

Recommended for interviews: Interviewers typically expect the linear scan solution using maintained boundaries (left maximum and right minimum). Starting with the brute force explanation shows you understand the problem definition, but the O(n) boundary detection demonstrates algorithmic maturity and efficient reasoning about sorted order violations.

Solution

We can enumerate every subarray of length k. For each subarray nums[i...i + k - 1], we need to find the smallest continuous segment such that, after sorting it, the entire subarray becomes non-decreasing.

For the subarray nums[i...i + k - 1], we can traverse from left to right, maintaining a maximum value mx. If the current value is less than mx, it means the current value is not in the correct position, so we update the right boundary r to the current position. Similarly, we can traverse from right to left, maintaining a minimum value mi. If the current value is greater than mi, it means the current value is not in the correct position, so we update the left boundary l to the current position. Initially, both l and r are set to -1. If neither l nor r is updated, it means the subarray is already sorted, so we return 0; otherwise, we return r - l + 1.

The time complexity is O(n times k), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window SortingO(n * k log k)O(k)Small constraints or when validating logic quickly
Monotonic Stack Boundary DetectionO(n)O(n)When detecting disorder boundaries using stack patterns
Left Max / Right Min EnumerationO(n)O(n)Optimal general solution for large arrays and interview settings

Video Solution

Smallest Subarray To Sort In Every Sliding Window • Owen Wu • 159 views views

Frequently Asked Questions

Is Smallest Subarray to Sort in Every Sliding Window easy or hard?
This problem is typically rated Medium because the brute force idea is simple but the optimal O(n) boundary detection requires recognizing sorted order violations. Understanding prefix maximums, suffix minimums, or monotonic stack patterns is key to solving it efficiently.
Smallest Subarray to Sort in Every Sliding Window Python/Java solution
The solution can be implemented in Python, Java, C++, Go, or TypeScript using the same linear scan idea. Track the running maximum during a forward pass and the running minimum during a backward pass to determine the minimal unsorted region in O(n) time.
How to solve Smallest Subarray to Sort in Every Sliding Window in O(n)?
Scan the array while maintaining the maximum value seen so far. If the current element is smaller than this maximum, it belongs to the unsorted region. Then perform a reverse scan tracking the minimum value from the right; elements larger than this minimum extend the right boundary. These two passes identify the minimal subarray that must be sorted.
What is the best approach for Smallest Subarray to Sort in Every Sliding Window?
The most efficient approach tracks violations of sorted order using a left maximum and right minimum scan. By maintaining the maximum element seen so far from the left and the minimum element from the right, you can detect the smallest boundaries that break sorted order. This method runs in O(n) time with O(n) extra space and avoids repeatedly sorting windows.
Is Smallest Subarray to Sort in Every Sliding Window asked at Google/Amazon/Meta?
Problems involving detecting minimal unsorted subarrays and sliding window analysis appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test array scanning techniques, monotonic stacks, and boundary detection logic rather than the exact problem statement.
What data structure is used in Smallest Subarray to Sort in Every Sliding Window?
The core solution primarily uses arrays with prefix and suffix tracking. Some variations use a monotonic stack to detect where sorted order breaks. These structures help detect disorder boundaries efficiently without sorting each window.
What is the time complexity of Smallest Subarray to Sort in Every Sliding Window?
The optimal solution runs in O(n) time using two linear passes across the array. One pass tracks the maximum value seen so far from the left, and another tracks the minimum value from the right. Brute force solutions that sort each window typically take O(n * k log k) time.

Ready to solve this problem?

Practice Smallest Subarray to Sort in Every Sliding Window with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shortest Unsorted Continuous Subarray