Minimum Swaps to Group All 1's Together

medium sliding window binary array counting

Problem

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. A swap exchanges the values of any two positions.

Inputdata = [1, 0, 1, 0, 1]

Output1

There are three 1's. Any window of length 3 holds at most two 1's, so we swap once to fill the remaining slot.

data (comma-separated 0/1)

def min_swaps(data):
    k = sum(data)
    if k == 0:
        return 0
    ones = sum(data[:k])
    best = ones
    for i in range(k, len(data)):
        ones += data[i] - data[i - k]
        best = max(best, ones)
    return k - best

function minSwaps(data) {
  const k = data.reduce((a, b) => a + b, 0);
  if (k === 0) return 0;
  let ones = 0;
  for (let i = 0; i < k; i++) ones += data[i];
  let best = ones;
  for (let i = k; i < data.length; i++) {
    ones += data[i] - data[i - k];
    best = Math.max(best, ones);
  }
  return k - best;
}

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

int minSwaps(vector<int>& data) {
    int k = 0;
    for (int v : data) k += v;
    if (k == 0) return 0;
    int ones = 0;
    for (int i = 0; i < k; i++) ones += data[i];
    int best = ones;
    for (int i = k; i < (int)data.size(); i++) {
        ones += data[i] - data[i - k];
        best = max(best, ones);
    }
    return k - best;
}

Explanation

The trick is to realize that grouping all the 1's together means they end up filling one solid block. That block has a fixed size: the total number of 1's, which we call k. So we only ever need to look at windows of length k.

For a window of size k, the 1's already inside it can stay; each 0 inside it needs one swap to be replaced by a 1 from outside. So swaps for that window equal k - (ones inside). To use the fewest swaps, we find the window that already contains the most 1's.

We compute ones for the first window data[0..k-1], then slide it forward one step at a time. Each slide adds data[i] and drops data[i - k], so updating the count is instant. We keep the largest count in best.

The answer is k - best. If there are no 1's at all (k == 0), there is nothing to group and we return 0.

Example: data = [1, 0, 1, 0, 1] has k = 3. The best window of length 3 holds two 1's, so best = 2 and the answer is 3 - 2 = 1 swap.

Time: O(n) Space: O(1)