##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2134.html

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

• Difficulty: Medium.
• Related Topics: Array, Sliding Window.
• Similar Questions: Minimum Swaps to Group All 1’s Together, Time Needed to Rearrange a Binary String.

## Problem

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.

## Solution (Java, C++, Python)

• class Solution {
public int minSwaps(int[] nums) {
int l = nums.length;
int[] ones = new int[l];
ones[0] = nums[0] == 1 ? 1 : 0;
for (int i = 1; i < l; i++) {
if (nums[i] == 1) {
ones[i] = ones[i - 1] + 1;
} else {
ones[i] = ones[i - 1];
}
}
if (ones[l - 1] == l || ones[l - 1] == 0) {
return 0;
}
int ws = ones[l - 1];
int minSwaps = Integer.MAX_VALUE;
int si = 0;
int ei;
while (si < nums.length) {
ei = (si + ws - 1) % l;
int totalones;
if (ei >= si) {
totalones = ones[ei] - (si == 0 ? 0 : ones[si - 1]);
} else {
totalones = ones[ei] + (ones[l - 1] - ones[si - 1]);
}
int swapsreq = ws - totalones;
if (swapsreq < minSwaps) {
minSwaps = swapsreq;
}
si++;
}
return minSwaps;
}
}

• Todo

• class Solution:
def minSwaps(self, nums: List[int]) -> int:
cnt = nums.count(1)
n = len(nums)
s = [0] * ((n << 1) + 1)
for i in range(n << 1):
s[i + 1] = s[i] + nums[i % n]
mx = 0
for i in range(n << 1):
j = i + cnt - 1
if j < (n << 1):
mx = max(mx, s[j + 1] - s[i])
return cnt - mx

############

# 2134. Minimum Swaps to Group All 1's Together II
# https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/

class Solution:
def minSwaps(self, nums: List[int]) -> int:
n = len(nums)
ones = nums.count(1)

nums = nums + nums
maxCount = 0

prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)

for i in range(n):
maxCount = max(maxCount, prefix[i + ones] - prefix[i])

return ones - maxCount



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).