3555. Smallest Subarray to Sort in Every Sliding Window 🔒
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.
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 <= 10001 <= k <= nums.length1 <= nums[i] <= 106
Solutions
Solution 1: Enumeration + Maintaining Left Maximum and Right Minimum
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 $\textit{nums}$. The space complexity is $O(1)$.
Python3
class Solution:
def minSubarraySort(self, nums: List[int], k: int) -> List[int]:
def f(i: int, j: int) -> int:
mi, mx = inf, -inf
l = r = -1
for k in range(i, j + 1):
if mx > nums[k]:
r = k
else:
mx = nums[k]
p = j - k + i
if mi < nums[p]:
l = p
else:
mi = nums[p]
return 0 if r == -1 else r - l + 1
n = len(nums)
return [f(i, i + k - 1) for i in range(n - k + 1)]
Java
class Solution {
private int[] nums;
private final int inf = 1 << 30;
public int[] minSubarraySort(int[] nums, int k) {
this.nums = nums;
int n = nums.length;
int[] ans = new int[n - k + 1];
for (int i = 0; i < n - k + 1; ++i) {
ans[i] = f(i, i + k - 1);
}
return ans;
}
private int f(int i, int j) {
int mi = inf, mx = -inf;
int l = -1, r = -1;
for (int k = i; k <= j; ++k) {
if (nums[k] < mx) {
r = k;
} else {
mx = nums[k];
}
int p = j - k + i;
if (nums[p] > mi) {
l = p;
} else {
mi = nums[p];
}
}
return r == -1 ? 0 : r - l + 1;
}
}
C++
class Solution {
public:
vector<int> minSubarraySort(vector<int>& nums, int k) {
const int inf = 1 << 30;
int n = nums.size();
auto f = [&](int i, int j) -> int {
int mi = inf, mx = -inf;
int l = -1, r = -1;
for (int k = i; k <= j; ++k) {
if (nums[k] < mx) {
r = k;
} else {
mx = nums[k];
}
int p = j - k + i;
if (nums[p] > mi) {
l = p;
} else {
mi = nums[p];
}
}
return r == -1 ? 0 : r - l + 1;
};
vector<int> ans;
for (int i = 0; i < n - k + 1; ++i) {
ans.push_back(f(i, i + k - 1));
}
return ans;
}
};
Go
func minSubarraySort(nums []int, k int) []int {
const inf = 1 << 30
n := len(nums)
f := func(i, j int) int {
mi := inf
mx := -inf
l, r := -1, -1
for p := i; p <= j; p++ {
if nums[p] < mx {
r = p
} else {
mx = nums[p]
}
q := j - p + i
if nums[q] > mi {
l = q
} else {
mi = nums[q]
}
}
if r == -1 {
return 0
}
return r - l + 1
}
ans := make([]int, 0, n-k+1)
for i := 0; i <= n-k; i++ {
ans = append(ans, f(i, i+k-1))
}
return ans
}
TypeScript
function minSubarraySort(nums: number[], k: number): number[] {
const inf = Infinity;
const n = nums.length;
const f = (i: number, j: number): number => {
let mi = inf;
let mx = -inf;
let l = -1,
r = -1;
for (let p = i; p <= j; ++p) {
if (nums[p] < mx) {
r = p;
} else {
mx = nums[p];
}
const q = j - p + i;
if (nums[q] > mi) {
l = q;
} else {
mi = nums[q];
}
}
return r === -1 ? 0 : r - l + 1;
};
const ans: number[] = [];
for (let i = 0; i <= n - k; ++i) {
ans.push(f(i, i + k - 1));
}
return ans;
}