LeetCode 3555 - Smallest Subarray to Sort in Every Sliding Window

The problem asks us to examine every contiguous subarray (window) of length k in the array nums and determine the minimum continuous segment within that window that must be sorted to make the entire window non-decreasing.

leetcodemediumarraytwo-pointersstackgreedysortingmonotonic-stack

LeetCode Problem 3555

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Stack, Greedy, Sorting, Monotonic Stack

Solution

Problem Understanding

The problem asks us to examine every contiguous subarray (window) of length k in the array nums and determine the minimum continuous segment within that window that must be sorted to make the entire window non-decreasing. In other words, for each sliding window, we want the smallest subarray that, if sorted, results in the window being sorted. If the window is already sorted, the required length is zero.

The input is an integer array nums of length n (1 <= n <= 1000) and an integer k (1 <= k <= n). Each integer in nums is positive (1 <= nums[i] <= 10^6). The output is an array of length n - k + 1, where each element corresponds to the minimum length of the subarray to sort for the respective window.

Important edge cases include windows that are already sorted (requiring length 0), windows that are fully decreasing (requiring length k), and windows containing repeated values, which can affect sorting decisions. The problem guarantees that nums is non-empty and that k is a valid window size, so no additional checks for invalid input are needed.

Approaches

Brute Force

The brute-force approach considers each window independently. For each window of length k, we can check all possible continuous subarrays, sort them, and test if the entire window becomes non-decreasing. While this approach is correct, it is highly inefficient. The number of subarrays in a window is O(k^2), and sorting each subarray takes O(k log k), so for n - k + 1 windows, the total time complexity is O((n - k + 1) * k^3 log k), which is unacceptable for n up to 1000.

Optimal Approach

The key observation is that, for each window, the smallest subarray to sort is determined by the positions where the order is violated. If we can track the indices where nums[i] > nums[i + 1] within the window, the subarray to sort is simply the segment from the first such violation to the last. A monotonic stack or a linear scan can efficiently compute this segment in O(k) per window. By sliding the window and updating this segment, we reduce unnecessary repeated computations.

Approach Time Complexity Space Complexity Notes
Brute Force O((n-k+1) * k^3 log k) O(k) Checks all possible subarrays within each window
Optimal O(n * k) O(k) Uses linear scan per window, finds first and last violation efficiently

Algorithm Walkthrough

  1. Initialize an empty list result to store the minimum subarray length for each window.
  2. Iterate over all windows nums[i:i+k] where i ranges from 0 to n-k.
  3. For each window, initialize two pointers left and right to track the first and last violations of the non-decreasing order.
  4. Perform a left-to-right scan to find the first index left where nums[j] > nums[j+1].
  5. Perform a right-to-left scan to find the last index right where nums[j-1] > nums[j].
  6. If no violations are found (left not set), append 0 to result.
  7. Otherwise, append right - left + 1 to result.
  8. Return result.

Why it works: Within any subarray, only the first and last violations determine the minimal continuous segment that disrupts non-decreasing order. Sorting this segment restores order for the entire window. By scanning left-to-right and right-to-left, we capture exactly this segment.

Python Solution

from typing import List

class Solution:
    def minSubarraySort(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        result = []
        
        for i in range(n - k + 1):
            window = nums[i:i+k]
            left, right = -1, -1
            
            # Find first violation from the left
            for j in range(k - 1):
                if window[j] > window[j + 1]:
                    left = j
                    break
            
            # Find first violation from the right
            for j in range(k - 1, 0, -1):
                if window[j - 1] > window[j]:
                    right = j
                    break
            
            if left == -1:  # Window is already sorted
                result.append(0)
            else:
                result.append(right - left + 1)
        
        return result

Implementation Walkthrough: The code iterates over all possible windows. For each window, it identifies the first and last violations of non-decreasing order. If no violations exist, the window is already sorted. Otherwise, it computes the length of the segment to sort using the indices of the first and last violations.

Go Solution

func minSubarraySort(nums []int, k int) []int {
    n := len(nums)
    result := make([]int, 0, n-k+1)
    
    for i := 0; i <= n-k; i++ {
        left, right := -1, -1
        window := nums[i : i+k]
        
        for j := 0; j < k-1; j++ {
            if window[j] > window[j+1] {
                left = j
                break
            }
        }
        
        for j := k - 1; j > 0; j-- {
            if window[j-1] > window[j] {
                right = j
                break
            }
        }
        
        if left == -1 {
            result = append(result, 0)
        } else {
            result = append(result, right-left+1)
        }
    }
    
    return result
}

Go-specific notes: Slices are used instead of arrays, preallocating result to avoid repeated resizing. The logic mirrors the Python version, handling empty windows naturally by the loop limits.

Worked Examples

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

Window window scan left->right window scan right->left Subarray length
[1,3,2] left=1 right=2 2
[3,2,4] left=0 right=1 2
[2,4,5] none none 0

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

Window window scan left->right window scan right->left Subarray length
[5,4,3,2] left=0 right=3 4
[4,3,2,1] left=0 right=3 4

Complexity Analysis

Measure Complexity Explanation
Time O(n * k) Each of the n-k+1 windows is scanned left and right, each scan is O(k)
Space O(n-k+1) Output array of length n-k+1; auxiliary storage for window is O(k)

The algorithm avoids sorting windows, which keeps complexity manageable for n ≤ 1000.

Test Cases

# Provided examples
assert Solution().minSubarraySort([1,3,2,4,5], 3) == [2,2,0]  # Example 1
assert Solution().minSubarraySort([5,4,3,2,1], 4) == [4,4]    # Example 2

# Edge cases
assert Solution().minSubarraySort([1,2,3,4,5], 5) == [0]      # Already sorted full array
assert Solution().minSubarraySort([1], 1) == [0]              # Single element window
assert Solution().minSubarraySort([2,1], 2) == [2]            # Two elements reversed

# Repeated elements
assert Solution().minSubarraySort([1,2,2,1], 3) == [2,2]      # Duplicates affect segment
Test Why
[1,3,2,4,5], k=3 Validates basic case with partial unsorted windows
[5,4,3,2,1], k=4 Validates completely reversed windows
[1,2,3,4,5], k=5 Already sorted full window
[1], k=1 Minimal input size
[2,1], k=2 Minimal window size with descending order
[1,2,2,1], k=3 Tests repeated elements affecting subarray length

Edge Cases

Single-element windows: When k = 1, each window is trivially sorted, so the algorithm must correctly return 0. This is handled because the left and right violation scans never find a violation, leaving left = -1.

Fully reversed windows: If a window is strictly decreasing, the subarray to sort is the entire