# 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⁵</code>
- <code>nums[i]</code> is either <code>0</code> or <code>1</code>.

## Solution 1 - Sliding Window
#### C++

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