# Minimum Swaps to Group All 1's Together II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-swaps-to-group-all-1's-together-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## 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`.

# Approaches
## Brute Force Iteration
This approach involves checking every possible contiguous block where all the 1s could be grouped. Since the array is circular, we iterate through all `n` possible starting points for a window of size `k` (where `k` is the total number of 1s). For each window, we count the number of 0s within it. The minimum count of 0s found among all possible windows is the minimum number of swaps required.
**Time:** O(N * K), where N is the length of the array and K is the total number of 1s. In the worst case, K can be close to N, making the complexity O(N^2). · **Space:** O(1), as we only use a few variables to store counts and indices, regardless of the input size.
**Pros:** Simple to understand and implement.; It correctly solves the problem for small inputs.
**Cons:** Highly inefficient due to its nested loops, resulting in a quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error for large input arrays as specified in the constraints.
### Explanation
The fundamental idea is to exhaustively check every potential final configuration. The final configuration will always be a contiguous block of `totalOnes` 1s. The number of swaps needed to achieve a specific configuration (a window filled with 1s) is equal to the number of 0s currently in that window's positions.

1.  First, we perform a single pass through the array to count the total number of 1s, let's call it `totalOnes`. This count determines the size of our target window.
2.  If `totalOnes` is 0 or equals the array's length, all elements are already grouped (or there are no 1s to group), so we need 0 swaps.
3.  We then iterate through each index `i` of the array, considering it as the starting point of our target window.
4.  For each starting index `i`, we define a window of size `totalOnes`. Due to the circular nature of the array, this window will cover indices from `i` to `i + totalOnes - 1`, wrapping around using the modulo operator (`% n`).
5.  We iterate through this window and count the number of 0s. This count represents the number of swaps needed to move all 1s into this specific window.
6.  We maintain a variable, `minSwaps`, and update it with the minimum count of 0s found so far.
7.  After checking all `n` possible starting positions, `minSwaps` will hold the answer.

```java
class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int totalOnes = 0;
        for (int x : nums) {
            if (x == 1) {
                totalOnes++;
            }
        }

        if (totalOnes == 0 || totalOnes == n) {
            return 0;
        }

        int minZeros = Integer.MAX_VALUE;

        // Iterate through all possible start positions of the window
        for (int i = 0; i < n; i++) {
            int currentZeros = 0;
            // Check the window of size totalOnes starting at i
            for (int j = 0; j < totalOnes; j++) {
                if (nums[(i + j) % n] == 0) {
                    currentZeros++;
                }
            }
            minZeros = Math.min(minZeros, currentZeros);
        }

        return minZeros;
    }
}
```
### Algorithm
- Calculate `totalOnes`, the total count of 1s in `nums`.
- If `totalOnes` is 0 or equals `nums.length`, return 0 as no swaps are needed.
- Initialize `minSwaps` to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through every possible starting index `i` from `0` to `nums.length - 1`.
- For each `i`, this marks the start of a potential window to group the 1s.
- Inside this loop, initialize a counter for zeros in the current window, `currentZeros = 0`.
- Start a second loop to iterate `j` from `0` to `totalOnes - 1` to build the window of size `totalOnes`.
- Calculate the index in the circular array using the modulo operator: `idx = (i + j) % nums.length`.
- If `nums[idx]` is 0, increment `currentZeros`.
- After the inner loop finishes, `currentZeros` holds the number of swaps required for the window starting at `i`.
- Update `minSwaps = min(minSwaps, currentZeros)`.
- After the outer loop completes, `minSwaps` will hold the minimum number of swaps required over all possible window positions. Return `minSwaps`.

## Sliding Window on a Doubled Array
A more efficient approach uses the sliding window technique. To easily handle the circular nature of the array, we can create a temporary array of twice the size by concatenating the original array with itself. Any circular window in the original array corresponds to a linear window in this new, larger array. We then apply a standard sliding window of size `k` (total number of 1s) on this new array to find the window with the maximum number of 1s, which corresponds to the minimum number of 0s.
**Time:** O(N), where N is the length of the array. We iterate through the array a constant number of times. · **Space:** O(N), as we need to create a new array of size 2N to store the doubled sequence.
**Pros:** Efficient linear time complexity, making it suitable for large inputs.; The logic of converting a circular problem to a linear one is a common and useful pattern.
**Cons:** Requires extra space proportional to the input size to store the doubled array.
### Explanation
The key insight is to simplify the circular array problem by converting it into a linear one. By creating a new array `doubledNums` of length `2*n` that is `nums` concatenated with itself, any window that wraps around in `nums` will appear as a contiguous, linear window in `doubledNums`.

1.  First, count the total number of 1s, `totalOnes`.
2.  Create the `doubledNums` array.
3.  The problem is now to find the subarray (window) of length `totalOnes` in `doubledNums` that contains the maximum number of 1s.
4.  We start by calculating the number of 1s in the first window of size `totalOnes` (from index 0 to `totalOnes - 1`). We'll call this `currentOnes` and initialize `maxOnes` with this value.
5.  Then, we slide this window one position at a time. We only need to check `n` unique windows, corresponding to the `n` possible start positions in the original circular array. The loop for the window's start index `i` will go from `1` to `n-1`.
6.  For each slide, we update `currentOnes` efficiently in O(1) time. We subtract the value of the element that just left the window's left edge and add the value of the new element that just entered on the right edge.
7.  We continuously update `maxOnes` with the maximum `currentOnes` seen.
8.  The minimum number of swaps is the size of the window (`totalOnes`) minus the maximum number of 1s we could fit into it (`maxOnes`). This difference gives the minimum number of 0s in any window.

```java
class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int totalOnes = 0;
        for (int x : nums) {
            totalOnes += x;
        }

        if (totalOnes == 0 || totalOnes == n) {
            return 0;
        }

        int[] doubledNums = new int[2 * n];
        System.arraycopy(nums, 0, doubledNums, 0, n);
        System.arraycopy(nums, 0, doubledNums, n, n);

        int currentOnes = 0;
        // Calculate ones in the first window
        for (int i = 0; i < totalOnes; i++) {
            currentOnes += doubledNums[i];
        }

        int maxOnes = currentOnes;
        // Slide the window across n possible start positions
        for (int i = 1; i < n; i++) {
            // Window moves from [i-1, i+totalOnes-2] to [i, i+totalOnes-1]
            currentOnes = currentOnes - doubledNums[i - 1] + doubledNums[i + totalOnes - 1];
            maxOnes = Math.max(maxOnes, currentOnes);
        }

        return totalOnes - maxOnes;
    }
}
```
### Algorithm
- Calculate `totalOnes`, the total count of 1s in `nums`.
- If `totalOnes` is 0 or `n`, return 0.
- Create a new array `doubledNums` of size `2 * n` by concatenating `nums` with itself. This transforms the circular problem into a linear one.
- Initialize a sliding window of size `totalOnes` on `doubledNums`.
- Calculate the number of 1s in the first window (from index 0 to `totalOnes - 1`). Let this be `currentOnes`.
- Initialize `maxOnes = currentOnes`.
- Slide the window from left to right across `n` possible starting positions. Iterate `i` from `1` to `n - 1`.
- In each step, update `currentOnes` in O(1) time by subtracting the value of the element leaving the window (`doubledNums[i - 1]`) and adding the value of the element entering the window (`doubledNums[i + totalOnes - 1]`).
- Update `maxOnes = max(maxOnes, currentOnes)` in each step.
- After the loop, `maxOnes` is the maximum number of 1s that can be found in any window of size `totalOnes`.
- The minimum number of swaps is `totalOnes - maxOnes`.

## Space-Optimized Sliding Window with Modulo Arithmetic
This is the most optimal approach. It builds upon the sliding window idea but avoids the O(N) space complexity of creating a doubled array. The circularity of the array is handled elegantly and efficiently by using the modulo operator (`%`) for calculating indices that would otherwise wrap around.
**Time:** O(N), where N is the length of the array. We perform a few passes over the array, each taking linear time. · **Space:** O(1), as we only use a few variables to store counts and indices, making it very memory-efficient.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; It's the most efficient solution for this problem.
**Cons:** The use of modulo arithmetic for indexing can be slightly less intuitive than the doubled array approach for some developers.
### Explanation
This approach refines the sliding window technique to achieve optimal space complexity. Instead of physically creating a doubled array, we simulate the behavior of a circular window on the original array.

1.  As before, we first count `totalOnes` to determine the window size.
2.  We compute the number of 1s in the initial window, which spans from index `0` to `totalOnes - 1`. This gives us our initial `currentOnes` and `maxOnes`.
3.  We then slide the window `n-1` more times to cover all possible circular starting positions. The loop for the window's start index `i` runs from `1` to `n-1`.
4.  In each iteration, we update `currentOnes`. The element leaving the window is at index `i - 1`. The element entering the window would be at index `i + totalOnes - 1` in a linear array. To handle the circularity, we find its actual index using the modulo operator: `(i + totalOnes - 1) % n`.
5.  The update rule is: `currentOnes = currentOnes - nums[i - 1] + nums[(i + totalOnes - 1) % n]`.
6.  We keep track of the maximum `currentOnes` seen in `maxOnes`.
7.  Finally, the minimum number of swaps is `totalOnes - maxOnes`, which represents the minimum number of 0s in any possible window.

This method provides the same linear time efficiency as the doubled array approach but with the significant advantage of constant space usage.

```java
class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int totalOnes = 0;
        for (int x : nums) {
            totalOnes += x;
        }

        if (totalOnes == 0 || totalOnes == n) {
            return 0;
        }

        int currentOnes = 0;
        // Calculate ones in the first window (from 0 to totalOnes-1)
        for (int i = 0; i < totalOnes; i++) {
            currentOnes += nums[i];
        }

        int maxOnes = currentOnes;
        // Slide the window and handle wrap-around with modulo
        for (int i = 1; i < n; i++) {
            // Element leaving is at i-1
            int leavingElement = nums[i - 1];
            // Element entering is at (i + totalOnes - 1) % n
            int enteringElement = nums[(i + totalOnes - 1) % n];
            
            currentOnes = currentOnes - leavingElement + enteringElement;
            maxOnes = Math.max(maxOnes, currentOnes);
        }

        return totalOnes - maxOnes;
    }
}
```
### Algorithm
- Calculate `totalOnes`, the total count of 1s in `nums`.
- If `totalOnes` is 0 or `n`, return 0.
- Calculate the number of 1s in the first window of size `totalOnes` (indices `0` to `totalOnes - 1`). Let this be `currentOnes`.
- Initialize `maxOnes = currentOnes`.
- Iterate `i` from `1` to `n - 1`. This `i` represents the starting index of the sliding window.
- The element leaving the window is at index `i - 1`.
- The element entering the window is at index `i + totalOnes - 1`. To handle the wrap-around, we calculate the actual index as `(i + totalOnes - 1) % n`.
- Update `currentOnes` in O(1) by subtracting `nums[i - 1]` and adding `nums[(i + totalOnes - 1) % n]`.
- Update `maxOnes = max(maxOnes, currentOnes)`.
- After iterating through all `n` possible starting positions, return `totalOnes - maxOnes`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinSwaps(int[] nums) {
        int k = nums.Sum();
        int n = nums.Length;
        int cnt = 0;
        for (int i = 0; i < k; ++i) {
            cnt += nums[i];
        }
        int mx = cnt;
        for (int i = k; i < n + k; ++i) {
            cnt += nums[i % n] - nums[(i - k + n) % n];
            mx = Math.Max(mx, cnt);
        }
        return k - mx;
    }
}
```

### Java

```java
class Solution {
public
  int minSwaps(int[] nums) {
    int cnt = 0;
    for (int v : nums) {
      cnt += v;
    }
    int n = nums.length;
    int[] s = new int[(n << 1) + 1];
    for (int i = 0; i < (n << 1); ++i) {
      s[i + 1] = s[i] + nums[i % n];
    }
    int mx = 0;
    for (int i = 0; i < (n << 1); ++i) {
      int j = i + cnt - 1;
      if (j < (n << 1)) {
        mx = Math.max(mx, s[j + 1] - s[i]);
      }
    }
    return cnt - mx;
  }
}

```

### JavaScript

```javascript
function minSwaps ( nums ) { const n = nums . length ; const k = nums . reduce (( a , b ) => a + b , 0 ); let cnt = k - nums . slice ( 0 , k ). reduce (( a , b ) => a + b , 0 ); let min = cnt ; for ( let i = k ; i < n + k ; i ++ ) { cnt += nums [ i - k ] - nums [ i % n ]; min = Math . min ( min , cnt ); } return min ; }
```

### CPP

```cpp
class Solution {
public:
  int minSwaps(vector<int> &nums) {
    int cnt = 0;
    for (int &v : nums)
      cnt += v;
    int n = nums.size();
    vector<int> s((n << 1) + 1);
    for (int i = 0; i < (n << 1); ++i)
      s[i + 1] = s[i] + nums[i % n];
    int mx = 0;
    for (int i = 0; i < (n << 1); ++i) {
      int j = i + cnt - 1;
      if (j < (n << 1))
        mx = max(mx, s[j + 1] - s[i]);
    }
    return cnt - mx;
  }
};

```

### Python

```python
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

```