Welcome to Subscribe On Youtube

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)$.

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

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


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

All Problems

All Solutions