3555. Smallest Subarray to Sort in Every Sliding Window 🔒

MediumStackGreedyArrayTwo PointersSortingMonotonic Stack

Problem Description

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.

For every subarray of length k, scan from left to right, maintaining the maximum value seen so far. If the current number is less than this maximum, that index is a candidate for the right boundary of an unsorted segment. Similarly, scan from right to left, maintaining the minimum value seen so far. If the current number is greater than this minimum, that index is a candidate for the left boundary of the segment. If there are no such indices, the subarray is already sorted. Otherwise, return the length between the left and right boundaries (inclusive) as the answer for this window.

Each entry in the result corresponds to one such window of size k in nums.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To make a subarray non-decreasing, we only need to identify the minimal part that is out of order and sort it. If we scan a window from left to right, any number that is less than the maximum we've seen so far is out of place and should be included in the segment we need to sort. Similarly, going from right to left, any number that's greater than the minimum we've seen so far is also out of place. This way, we mark the earliest and latest points where numbers break the order. Sorting this segment will make the whole window non-decreasing with the smallest possible effort. If no such points are found, the window is already sorted, so nothing needs to be done.

Solution Approach

For each subarray of length k in nums, we find the minimum length of a segment to sort so the entire subarray becomes non-decreasing.

We process each window from index i to i + k - 1 with the following steps:

Left-to-right traversal: Keep a running maximum value (mx). For each index in the window, if nums[index] is less than mx, it means this number is "out of order" with what has come before and indicates an unsorted portion to the right. Update the right boundary (r) to the current index. Otherwise, update mx to the current number.
Right-to-left traversal: Keep a running minimum value (mi). For each index in the window from right to left, if nums[index] is greater than mi, this number is larger than something after it and thus out of order. Update the left boundary (l) to the current index. Otherwise, update mi to the current number.
Result for this window:
- If neither l nor r was updated (remain -1), then the subarray is already sorted, and the result is 0.
- Otherwise, the minimal segment to sort is from l to r, inclusive, so the answer is r - l + 1.

These steps produce an answer for each window. Collect all answers into an array and return it.

Pseudocode outline:

for each window [i, i + k - 1]:
    l, r = -1, -1
    mx = -inf
    for j in i to i + k - 1:
        if nums[j] < mx:
            r = j
        else:
            mx = nums[j]
    mi = inf
    for j in i + k - 1 down to i:
        if nums[j] > mi:
            l = j
        else:
            mi = nums[j]
    if l == -1:
        result.append(0)
    else:
        result.append(r - l + 1)

This uses a linear scan for each window and simple variables to track bounds, making the algorithm easy to implement and efficient for the intended window size.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the approach with an example:

Suppose nums = [1, 3, 2, 4, 5] and k = 4. So, our windows are:

[1, 3, 2, 4]
[3, 2, 4, 5]

Let's process each window:

Window 1: [1, 3, 2, 4] (indices 0 to 3)

Step 1: Left-to-right traversal (find r)

Initial mx = -inf, r = -1.
At index 0: nums[0]=1 > mx (-inf) ⇒ update mx=1.
At index 1: nums[1]=3 > mx=1 ⇒ update mx=3.
At index 2: nums[2]=2 < mx=3 ⇒ out of order → set r=2.
At index 3: nums[3]=4 > mx=3 ⇒ update mx=4.

Final r = 2.

Step 2: Right-to-left traversal (find l)

Initial mi = inf, l = -1.
At index 3: nums[3]=4 < mi ⇒ update mi=4.
At index 2: nums[2]=2 < mi=4 ⇒ update mi=2.
At index 1: nums[1]=3 > mi=2 ⇒ out of order → set l=1.
At index 0: nums[0]=1 < mi=2 ⇒ update mi=1.

Final l = 1.

The segment to sort: indices 1..2 (values [3, 2]), length = r - l + 1 = 2.

Window 2: [3, 2, 4, 5] (indices 1 to 4)

Left-to-right:

mx = -inf, r=-1
idx 1: nums[1]=3 > mx ⇒ update mx=3
idx 2: nums[2]=2 < mx=3 ⇒ set r=2
idx 3: nums[3]=4 > mx ⇒ update mx=4
idx 4: nums[4]=5 > mx=4 ⇒ update mx=5

Final r=2

Right-to-left:

mi=inf, l=-1
idx 4: nums[4]=5 < mi ⇒ update mi=5
idx 3: nums[3]=4 < mi=5 ⇒ update mi=4
idx 2: nums[2]=2 < mi=4 ⇒ update mi=2
idx 1: nums[1]=3 > mi=2 ⇒ set l=1

Final l=1

Segment: indices 1..2 ([2, 4]), so answer is 2.

Result: For both windows, the minimal length to sort so the whole window becomes non-decreasing is 2.

Final output: [2, 2]

Solution Implementation

1from math import inf
2from typing import List
3
4class Solution:
5    def minSubarraySort(self, nums: List[int], k: int) -> List[int]:
6        # Helper function to determine the size of the minimal subarray (within nums[i:j+1])
7        # that, when sorted, results in the subarray being sorted.
8        def f(i: int, j: int) -> int:
9            min_num = inf      # The minimal number found in suffix order
10            max_num = -inf     # The maximal number found in prefix order
11            left = -1          # The left boundary of the minimal unsorted subarray
12            right = -1         # The right boundary of the minimal unsorted subarray
13
14            for idx in range(i, j + 1):
15                # Check from left to right for any disorder (increasing max_num)
16                if max_num > nums[idx]:
17                    right = idx
18                else:
19                    max_num = nums[idx]
20
21                # Check from right to left for any disorder (decreasing min_num)
22                reverse_idx = j - (idx - i)
23                if min_num < nums[reverse_idx]:
24                    left = reverse_idx
25                else:
26                    min_num = nums[reverse_idx]
27            # If the subarray is already sorted, return 0; otherwise, return the size
28            return 0 if right == -1 else right - left + 1
29
30        n = len(nums)
31        # For every subarray of size k, apply the helper function f
32        return [f(i, i + k - 1) for i in range(n - k + 1)]
33

1class Solution {
2    private int[] nums;
3    private final int INF = 1 << 30; // A large constant used as "infinity"
4
5    // Main method to find the minimal subarray that needs to be sorted for every window of size k
6    public int[] minSubarraySort(int[] nums, int k) {
7        this.nums = nums;
8        int n = nums.length;
9        int[] answer = new int[n - k + 1];
10        // Slide a window of size k across the array and calculate answer for each window
11        for (int i = 0; i <= n - k; ++i) {
12            answer[i] = f(i, i + k - 1);
13        }
14        return answer;
15    }
16
17    // Helper function to compute minimal subarray to sort in window [i, j]
18    private int f(int left, int right) {
19        int minVal = INF, maxVal = -INF;
20        int minSubLeft = -1, minSubRight = -1;
21        // Traverse from left to right and right to left within the window
22        for (int idx = left; idx <= right; ++idx) {
23            // From left to right: track the rightmost index to fix
24            if (nums[idx] < maxVal) {
25                minSubRight = idx;
26            } else {
27                maxVal = nums[idx];
28            }
29            // From right to left: track the leftmost index to fix
30            int mirroredIdx = right - (idx - left);
31            if (nums[mirroredIdx] > minVal) {
32                minSubLeft = mirroredIdx;
33            } else {
34                minVal = nums[mirroredIdx];
35            }
36        }
37        // If already sorted, return 0; otherwise, return the length of the subarray to sort
38        return minSubRight == -1 ? 0 : minSubRight - minSubLeft + 1;
39    }
40}
41

1class Solution {
2public:
3    // Function to find for every subarray of length k, the smallest subarray length to sort to make it sorted
4    vector<int> minSubarraySort(vector<int>& nums, int k) {
5        const int INF = 1 << 30;
6        int n = nums.size();
7
8        // Helper function: Given indices left and right,
9        // find the minimal length of a subarray inside nums[left...right]
10        // which, if sorted, makes the subarray sorted.
11        auto findMinSortWindow = [&](int left, int right) -> int {
12            int minVal = INF, maxVal = -INF;
13            int disorderLeft = -1, disorderRight = -1;
14
15            // Scan from left to right and record the last index where an inversion is detected
16            for (int i = left; i <= right; ++i) {
17                if (nums[i] < maxVal) {
18                    disorderRight = i;
19                } else {
20                    maxVal = nums[i];
21                }
22
23                // Symmetrical scan from right to left (using index p)
24                int p = right - (i - left);
25                if (nums[p] > minVal) {
26                    disorderLeft = p;
27                } else {
28                    minVal = nums[p];
29                }
30            }
31
32            // If never found disorder, subarray already sorted
33            return disorderRight == -1 ? 0 : disorderRight - disorderLeft + 1;
34        };
35
36        vector<int> result;
37        // Slide a window of length k over nums
38        for (int start = 0; start <= n - k; ++start) {
39            // For the window nums[start ... start + k - 1]
40            result.push_back(findMinSortWindow(start, start + k - 1));
41        }
42        return result;
43    }
44};
45

1/**
2 * Calculates the minimum subarray length in a window of size k that needs to be sorted
3 * so that the whole window is sorted. Slides the window across the array and computes
4 * the answer for each window.
5 *
6 * @param nums - The input array of numbers.
7 * @param k - The size of the sliding window.
8 * @returns An array where each element is the minimum subarray length to sort within each window.
9 */
10function minSubarraySort(nums: number[], k: number): number[] {
11    const INF = Infinity;
12    const n = nums.length;
13
14    /**
15     * For a given window [start, end], computes the minimal subarray length
16     * needing to be sorted so that the window becomes sorted.
17     *
18     * @param start - Start index of the window.
19     * @param end - End index of the window.
20     * @returns Length of minimal subarray to sort. 0 if the window is already sorted.
21     */
22    const windowSortLength = (start: number, end: number): number => {
23        let minVal = INF;     // Tracks minimum value scanning from right to left
24        let maxVal = -INF;    // Tracks maximum value scanning from left to right
25        let left = -1;        // Left bound of wrong order
26        let right = -1;       // Right bound of wrong order
27
28        for (let i = start; i <= end; ++i) {
29            // Scan from left to right to find first inversion for 'right'
30            if (nums[i] < maxVal) {
31                right = i;
32            } else {
33                maxVal = nums[i];
34            }
35
36            // Scan from right to left to find first inversion for 'left'
37            const j = end - (i - start);
38            if (nums[j] > minVal) {
39                left = j;
40            } else {
41                minVal = nums[j];
42            }
43        }
44        // If no disorder found (right == -1), the window is already sorted
45        return right === -1 ? 0 : right - left + 1;
46    };
47
48    const result: number[] = [];
49    // Slide a window of size k
50    for (let start = 0; start <= n - k; ++start) {
51        result.push(windowSortLength(start, start + k - 1));
52    }
53    return result;
54}
55

Time and Space Complexity

The time complexity of the code is O(n * k), where n is the length of the array nums. This is because the function f is called n - k + 1 times, and each call processes a subarray of length k, resulting in O(k) work per call.

The space complexity is O(1), as the algorithm uses only a constant amount of extra space regardless of the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: