Minimum Swaps to Group All 1's Together

Minimum Swaps to Group All 1's Together

What is this problem about?

The Minimum Swaps to Group All 1's Together problem gives you a binary array. In one swap, you can exchange any two elements. Find the minimum number of swaps to group all 1s into a contiguous segment. This Minimum Swaps to Group All 1's Together interview question is a clean fixed-size sliding window problem with an elegant observation at its core.

Why is this asked in interviews?

Expedia asks this to verify understanding of the fixed-size sliding window pattern and the insight of counting "what must change" within a window rather than simulating swaps. The array and sliding window interview pattern is directly demonstrated, and the key observation — the window size equals the count of 1s — rewards clear problem understanding.

Algorithmic pattern used

Fixed-size sliding window. Count total 1s in the array — call it ones. This is the target window size (since all 1s must end up in a window of this size). Slide a window of size ones across the array. For each window position, count the number of 0s inside it — these 0s need to be swapped out with 1s from outside. Track the minimum 0-count across all windows. That minimum equals the minimum swaps needed.

Example explanation

Array: [1, 0, 1, 0, 1]. Total 1s = 3. Window size = 3.

• Window [0..2] = [1,0,1]: zeros = 1 → 1 swap.
• Window [1..3] = [0,1,0]: zeros = 2 → 2 swaps.
• Window [2..4] = [1,0,1]: zeros = 1 → 1 swap. Minimum swaps = 1.

Common mistakes candidates make

• Thinking this requires sorting or a complex swap simulation.
• Not recognizing that the window size equals the number of 1s in the array.
• Recomputing zeros from scratch for each window instead of sliding.
• Forgetting to count zeros (not ones) inside the window as the cost metric.

Interview preparation tip

This problem beautifully demonstrates why sliding windows are powerful: instead of thinking about "which swaps to make," reframe to "find the window of size k with the most 1s already in place." The ones outside the window will naturally swap with zeros inside. This reframing technique — converting an action-based problem into an observation-based one — is a critical thinking skill. Practice similar problems where "minimum operations" equals "maximum already-correct elements."