2134. Minimum Swaps to Group All 1’s Together II LeetCode Solution

In this guide, you will get 2134. Minimum Swaps to Group All 1’s Together II LeetCode Solution with the best time and space complexity. The solution to Minimum Swaps to Group All ‘s Together II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Swaps to Group All ‘s Together II solution in C++
4. Minimum Swaps to Group All ‘s Together II solution in Java
5. Minimum Swaps to Group All ‘s Together II solution in Python
6. Additional Resources

Problem Statement of Minimum Swaps to Group All ‘s Together II

A swap is defined as taking two distinct positions in an array and swapping the values in them.
A circular array is defined as an array where we consider the first element and the last element to be adjacent.
Given a binary circular array nums, return the minimum number of swaps required to group all 1’s present in the array together at any location.

Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1’s together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1’s together with 0 swaps.
Thus, the minimum number of swaps required is 1.

Example 2:

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1’s together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1’s together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1’s are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

Constraints:

1 <= nums.length <= 105
nums[i] is either 0 or 1.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

2134. Minimum Swaps to Group All 1’s Together II LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2134. Minimum Swaps to Group All 1’s Together II LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

2134. Minimum Swaps to Group All 1’s Together II LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.