Skip to content

2134. Minimum Swaps to Group All 1's Together II 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int minSwaps(vector<int>& nums) {
    const int n = nums.size();
    const int k = ranges::count(nums, 1);
    int ones = 0;     // the number of ones in the window
    int maxOnes = 0;  // the maximum number of ones in the window

    for (int i = 0; i < n * 2; ++i) {
      if (i >= k && nums[(i - k) % n])
        --ones;
      if (nums[i % n])
        ++ones;
      maxOnes = max(maxOnes, ones);
    }

    return k - maxOnes;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int minSwaps(int[] nums) {
    final int n = nums.length;
    final int k = (int) Arrays.stream(nums).filter(a -> a == 1).count();
    int ones = 0;    // the number of ones in the window
    int maxOnes = 0; // the maximum number of ones in the window

    for (int i = 0; i < n * 2; ++i) {
      if (i >= k && nums[(i - k) % n] == 1)
        --ones;
      if (nums[i % n] == 1)
        ++ones;
      maxOnes = Math.max(maxOnes, ones);
    }

    return k - maxOnes;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def minSwaps(self, nums: list[int]) -> int:
    n = len(nums)
    k = nums.count(1)
    ones = 0  # the number of ones in the window
    maxOnes = 0  # the maximum number of ones in the window

    for i in range(n * 2):
      if i >= k and nums[i % n - k]:  # Magic in Python :)
        ones -= 1
      if nums[i % n]:
        ones += 1
      maxOnes = max(maxOnes, ones)

    return k - maxOnes