Minimum Swaps to Group All 1s Together

Problem Overview

You are given a binary array (containing only 0s and 1s). Your goal is to find the minimum number of swaps required to group all the 1s together in a continuous subarray.

A swap can happen between any two indices, not necessarily adjacent ones.

Why This Problem Is Tricky

At first glance, you might think:

“Let me try all possible swaps and find the minimum.”

That approach would be too slow (O(n²) or worse).

Instead, there’s a smarter way — using the Sliding Window Technique.

Key Insight (Most Important Part)

If there are k ones in the array, then in the final arrangement:

All 1s must occupy a contiguous block of size k

So instead of actually swapping:

• We imagine a window of size k

• We check how many 0s are inside this window

Why?

Each 0 inside the window must be swapped with a 1 outside.

So:

Minimum swaps = Number of 0s inside the best window

Step-by-Step Approach

• Count total number of 1s → k

• If k == 0, return -1

• Take a window of size k

• Count how many 1s are inside this window

• Slide the window across the array

• Track the maximum number of 1s in any window

Final answer:

k - maxOnes

Example Walkthrough

Input:

arr = [1, 0, 1, 0, 1]

Step 1:

Total 1s → k = 3

Step 2:

Check all windows of size 3:

• Window: [1, 0, 1]
  Ones Count: 2

• Window: [0, 1, 0]
  Ones Count: 1

• Window: [1, 0, 1]
  Ones Count: 2

Maximum ones in a window = 2

Step 3:

Swaps = k - maxOnes = 3 - 2 = 1

Output:

1

Another Example

Input:

arr = [1, 0, 1, 0, 1, 1]

• Total 1s = 4

• Best window contains 3 ones

Swaps = 4 - 3 = 1

Output:

1

Edge Case

Input:

arr = [0, 0, 0]

• No 1s present

Output:

-1

C# Implementation

class Solution {
    public int MinSwaps(int[] arr) {
        int n = arr.Length;

        // Step 1: Count total 1s
        int k = 0;
        foreach (int num in arr) {
            if (num == 1) k++;
        }

        // Edge case
        if (k == 0) return -1;

        // Step 2: First window
        int currOnes = 0;
        for (int i = 0; i < k; i++) {
            if (arr[i] == 1) currOnes++;
        }

        int maxOnes = currOnes;

        // Step 3: Sliding window
        for (int i = k; i < n; i++) {
            if (arr[i] == 1) currOnes++;
            if (arr[i - k] == 1) currOnes--;

            if (currOnes > maxOnes)
                maxOnes = currOnes;
        }

        return k - maxOnes;
    }
}

Complexity Analysis

• Time: O(n)

• Space: O(1)

Final Takeaway

Instead of thinking about swaps, think about:

“Where should all the 1s go?”

Then:

• Fix a window

• Optimize what’s already correct inside it

This mindset is key to mastering sliding window problems.

Summary

This article explains how to determine the minimum number of swaps required to group all 1s together in a binary array using a sliding window approach by identifying the optimal window of size k that maximizes the number of existing 1s, resulting in an efficient O(n) time and O(1) space solution.