---
# System prepended metadata

title: LC 2134. Minimum Swaps to Group All 1's Together II
tags: [medium, leedcode, Sliding Window, c++]

---

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

### [Problem link](https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/)

###### tags: `leedcode` `medium` `c++` `Sliding Window`

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 <code>nums</code>, return the minimum number of swaps required to group all <code>1</code>'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:** 

- <code>1 <= nums.length <= 10<sup>5</sup></code>
- <code>nums[i]</code> is either <code>0</code> or <code>1</code>.

## Solution 1 - Sliding Window
#### C++
```cpp=
class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int cnt1 = accumulate(nums.begin(), nums.end(), 0);

        int cnt = 0;
        for (int i = 0; i < cnt1; i++) {
            cnt += nums[i];
        }
        int ans = cnt1 - cnt;

        for (int i = 0; i < nums.size(); i++) {
            if (cnt1 - 1 - i >= 0) {
                cnt -= nums[cnt1 - 1 - i];
            } else {
                cnt -= nums[nums.size() + (cnt1 - 1 - i)];
            }
            cnt += nums[nums.size() - 1 - i];
            ans = min(ans, cnt1 - cnt);
        }
        return ans;
    }
};
```

>### Complexity
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(1)             |

## Note
x
