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 <= 1000
• 1 <= k <= nums.length
• 1 <= 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)\).

Python3JavaC++GoTypeScript

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)]

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;
    }
}

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;
    }
};

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
}

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;
}

Comments