Minimum Swaps to Group All 1's Together II

Minimum Swaps to Group All 1's Together II - Problem

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.

Input & Output

Example 1 — Basic Circular Array

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

› Output: 1

💡 Note: There are 3 ones total. We need a window of size 3. The best window is [1,1,0] which has only 1 zero, so we need 1 swap to group all 1's together.

Example 2 — All Ones Already

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

› Output: 0

💡 Note: All elements are already 1's, so no swaps are needed to group them together.

Example 3 — Circular Wrapping

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

› Output: 1

💡 Note: There are 2 ones. Due to circular nature, we can group them as [1,1] by using positions 0 and 4, requiring 1 swap.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Binary circular array [0,1,0,1,1,0,0] with 3 ones

Find Optimal Window

Window size = 3, find position with minimum zeros

Count Swaps

Minimum zeros in any window = minimum swaps needed

Key Takeaway

🎯 Key Insight: Use sliding window of size equal to total 1's count to efficiently find optimal grouping position

Asked in

F Facebook 25 A Amazon 20 G Google 15

The key insight is to use a sliding window of size equal to the number of 1's in the array. Since the array is circular, we can try all possible positions for grouping the 1's together. The optimal approach uses a sliding window technique to count zeros in each possible window position in O(n) time, where the minimum number of zeros equals the minimum swaps needed.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Positions	O(n²)	O(1)	Check every possible consecutive position to group all 1's together
Sliding Window - Optimal Solution	O(n)	O(1)	Use sliding window to efficiently check all possible grouping positions

Brute Force - Try All Positions — Algorithm Steps

Count total number of 1's in array
For each starting position, check window of size equal to 1's count
Calculate swaps needed (number of 0's in current window)
Return minimum swaps across all positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Count 1's

Total ones = 3, so window size = 3

Try Each Position

Check windows starting at each index

Count Zeros

Zeros in window = swaps needed

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int onesCount = 0;
    for (int i = 0; i < numsSize; i++) {
        onesCount += nums[i];
    }
    
    if (onesCount == 0 || onesCount == numsSize) {
        return 0;
    }
    
    int minSwaps = numsSize;
    
    // Try each starting position
    for (int start = 0; start < numsSize; start++) {
        int zerosInWindow = 0;
        // Count zeros in current window
        for (int i = 0; i < onesCount; i++) {
            int pos = (start + i) % numsSize;
            if (nums[pos] == 0) {
                zerosInWindow++;
            }
        }
        if (zerosInWindow < minSwaps) {
            minSwaps = zerosInWindow;
        }
    }
    
    return minSwaps;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int size = 0;
    char* ptr = line + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        nums[size++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        if (*ptr == ',') ptr++;
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop iterates n positions, inner operations count elements in each window

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track counts and minimum

✓ Linear Space

28.5K Views

Medium Frequency

~25 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

Brute Force - Try All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler