Minimum Swaps to Group All 1's Together - Practice Coding Problems

Minimum Swaps to Group All 1's Together - 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 is defined as exchanging the positions of any two elements in the array. The goal is to make all 1's contiguous (adjacent to each other) with the minimum number of swaps.

Note: The 1's can be grouped anywhere in the array - at the beginning, middle, or end.

Input & Output

Example 1 — Basic Case

$ Input: data = [1,0,1,0,1]

› Output: 1

💡 Note: We have 3 ones total. The optimal window is either [1,0,1] at positions 0-2 or 2-4, both containing 2 ones and 1 zero. We need 1 swap to make it all ones.

Example 2 — Already Grouped

$ Input: data = [0,0,1,1,1,0,0]

› Output: 0

💡 Note: All 3 ones are already grouped together at positions 2-4, so no swaps needed.

Example 3 — All Zeros or Ones

$ Input: data = [1,1,1,1]

› Output: 0

💡 Note: All elements are 1s, so they're already grouped together.

Constraints

1 ≤ data.length ≤ 10⁵
data[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Binary array [1,0,1,0,1] with scattered 1's

Find Window

Find window of size=ones_count with most 1's

Calculate

Swaps = window_size - max_ones_in_window

Output

Return minimum swaps needed: 1

Key Takeaway

🎯 Key Insight: Find the window of size k (number of 1's) that already contains the most 1's - this minimizes swaps needed

Asked in

M Microsoft 35 A Amazon 28 F Facebook 22 G Google 18

The key insight is to find the window of size equal to the number of 1's that contains the maximum number of 1's already. The minimum swaps needed equals the window size minus the maximum 1's found in any window. Best approach uses sliding window technique for O(n) time complexity. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window Optimization	O(n)	O(1)	Use sliding window to efficiently find the window with maximum 1's
Brute Force - Try All Positions	O(n²)	O(1)	Try grouping 1's at every possible position and count swaps needed

Sliding Window Optimization — Algorithm Steps

Count total 1's to determine window size
Initialize window with first k elements
Slide window right, updating count efficiently
Track maximum 1's found in any window

Visualization

Tap to expand

Step-by-Step Walkthrough

Window Size

Total ones = 3, so window size = 3

First Window

Window [1,0,1] has 2 ones

Slide Right

Remove 1, add 0: window [0,1,0] has 1 one

Slide Again

Remove 0, add 1: window [1,0,1] has 2 ones

Result

Max ones = 2, so min swaps = 3-2 = 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* data, int size) {
    int onesCount = 0;
    for (int i = 0; i < size; i++) {
        onesCount += data[i];
    }
    
    if (onesCount <= 1) {
        return 0;
    }
    
    // Count 1's in first window
    int currentOnes = 0;
    for (int i = 0; i < onesCount; i++) {
        currentOnes += data[i];
    }
    int maxOnesInWindow = currentOnes;
    
    // Slide the window
    for (int i = onesCount; i < size; i++) {
        // Remove leftmost element, add rightmost element
        currentOnes = currentOnes - data[i - onesCount] + data[i];
        maxOnesInWindow = max(maxOnesInWindow, currentOnes);
    }
    
    // Minimum swaps = window_size - max_ones_in_window
    return onesCount - maxOnesInWindow;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int data[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        data[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(data, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with constant time window updates

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track window state, no extra arrays

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler