Skip to content

3555. Smallest Subarray to Sort in Every Sliding Window 👍

  • Time: $O(nk)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<int> minSubarraySort(vector<int>& nums, int k) {
    const int n = nums.size();
    vector<int> ans;

    for (int i = 0; i <= n - k; ++i) {
      vector<int> window(nums.begin() + i, nums.begin() + i + k);
      vector<int> sortedWindow = window;
      ranges::sort(sortedWindow);
      int l = 0;
      int r = k - 1;
      while (l < k && window[l] == sortedWindow[l])
        ++l;
      while (r >= 0 && window[r] == sortedWindow[r])
        --r;
      ans.push_back(l > r ? 0 : r - l + 1);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int[] minSubarraySort(int[] nums, int k) {
    final int n = nums.length;
    int[] ans = new int[n - k + 1];

    for (int i = 0; i <= n - k; ++i) {
      int[] window = Arrays.copyOfRange(nums, i, i + k);
      int[] sortedWindow = window.clone();
      Arrays.sort(sortedWindow);
      int l = 0;
      int r = k - 1;
      while (l < k && window[l] == sortedWindow[l])
        ++l;
      while (r >= 0 && window[r] == sortedWindow[r])
        --r;
      ans[i] = l > r ? 0 : r - l + 1;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minSubarraySort(self, nums: list[int], k):
    ans = []

    for i in range(len(nums) - k + 1):
      window = nums[i:i+k]
      sortedWindow = sorted(window)
      l = 0
      r = k - 1
      while l < k and window[l] == sortedWindow[l]:
        l += 1
      while r >= 0 and window[r] == sortedWindow[r]:
        r -= 1
      ans.append(0 if l > r else r - l + 1)

    return ans