Smallest subarray to sort in every sliding window

Array Two Pointers Stack Greedy Sorting Monotonic Stack

59.0% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_subarray_sort(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let n = nums.len();
    let k = k as usize;
    let mut result = Vec::with_capacity(n - k + 1);
    
    for i in 0..=n - k {
      let window = &nums[i..i + k];
      // Find the minimum subarray that needs to be sorted.
      // Find leftmost and rightmost positions where window differs from sorted version.
      let mut sorted = window.to_vec();
      sorted.sort();
      
      let mut left = k;
      let mut right = 0;
      for j in 0..k {
        if window[j] != sorted[j] {
          if left == k { left = j; }
          right = j;
        }
      }
      
      if left == k {
        result.push(0);
      } else {
        result.push((right - left + 1) as i32);
      }
    }
    
    result
  }
}