# 1151. Minimum Swaps to Group All 1’s Together

## Description

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.


Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: Since there is only one 1 in the array, no swaps are needed.


Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].


Constraints:

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

## Solutions

Solution 1: Sliding Window

First, we count the number of $1$s in the array, denoted as $k$. Then we use a sliding window of size $k$, moving the right boundary of the window from left to right, and count the number of $1$s in the window, denoted as $t$. Each time we move the window, we update the value of $t$. Finally, when the right boundary of the window moves to the end of the array, the number of $1$s in the window is the maximum, denoted as $mx$. The final answer is $k - mx$.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array.

• class Solution {
public int minSwaps(int[] data) {
int k = 0;
for (int v : data) {
k += v;
}
int t = 0;
for (int i = 0; i < k; ++i) {
t += data[i];
}
int mx = t;
for (int i = k; i < data.length; ++i) {
t += data[i];
t -= data[i - k];
mx = Math.max(mx, t);
}
return k - mx;
}
}

• class Solution {
public:
int minSwaps(vector<int>& data) {
int k = 0;
for (int& v : data) {
k += v;
}
int t = 0;
for (int i = 0; i < k; ++i) {
t += data[i];
}
int mx = t;
for (int i = k; i < data.size(); ++i) {
t += data[i];
t -= data[i - k];
mx = max(mx, t);
}
return k - mx;
}
};

• class Solution:
def minSwaps(self, data: List[int]) -> int:
k = data.count(1)
t = sum(data[:k])
mx = t
for i in range(k, len(data)):
t += data[i]
t -= data[i - k]
mx = max(mx, t)
return k - mx


• func minSwaps(data []int) int {
k := 0
for _, v := range data {
k += v
}
t := 0
for _, v := range data[:k] {
t += v
}
mx := t
for i := k; i < len(data); i++ {
t += data[i]
t -= data[i-k]
mx = max(mx, t)
}
return k - mx
}

• function minSwaps(data: number[]): number {
const k = data.reduce((acc, cur) => acc + cur, 0);
let t = data.slice(0, k).reduce((acc, cur) => acc + cur, 0);
let mx = t;
for (let i = k; i < data.length; ++i) {
t += data[i] - data[i - k];
mx = Math.max(mx, t);
}
return k - mx;
}


• public class Solution {
public int MinSwaps(int[] data) {
int k = data.Count(x => x == 1);
int t = data.Take(k).Sum();
int mx = t;
for (int i = k; i < data.Length; ++i) {
t += data[i];
t -= data[i - k];
mx = Math.Max(mx, t);
}
return k - mx;
}
}