Minimum Swaps to group all Ones together

XXX. Minimum Swaps to Group All 1's

Array

Sliding Window

Problem Statement:

Given a binary array data, return the minimum number of swaps required to group all 1's together in a contiguous subarray.

• Array contains only 0s and 1s
• All 1's must be adjacent after swaps
• Only adjacent swaps are allowed

Algorithm:

1. **Key Insight**:
   • Final array must have all 1's together
   • Window size equals total number of 1's
   • Required swaps = Total 1's - Max 1's in window
2. **Sliding Window**:
   • Maintain fixed-size window
   • Count 1's in current window
   • Track maximum 1's seen in any window

Complexity:

Time Complexity: O(n), one pass through array
Space Complexity: O(1), constant extra space

Implementation:

Java Solution:

public int minSwaps(int[] data) {
    int ones = Arrays.stream(data).sum();          // Total number of 1's
    int cntOne = 0, maxOne = 0;
    int left = 0, right = 0;
    
    while (right < data.length) {
        cntOne += data[right++];                   // Add new element
        
        if (right - left > ones)                   // Maintain window size
            cntOne -= data[left++];
            
        maxOne = Math.max(maxOne, cntOne);         // Update maximum 1's seen
    }
    
    return ones - maxOne;                          // Minimum swaps needed
}
                

Python Solution:

def minSwaps(self, data: List[int]) -> int:
    ones = sum(data)                              # Total number of 1's
    cnt_one = max_one = 0
    left = right = 0
    
    while right < len(data):
        cnt_one += data[right]                    # Add new element
        right += 1
        
        if right - left > ones:                   # Maintain window size
            cnt_one -= data[left]
            left += 1
            
        max_one = max(max_one, cnt_one)          # Update maximum 1's seen
    
    return ones - max_one                         # Minimum swaps needed
                

C++ Solution:

int minSwaps(vector& data) {
    int ones = accumulate(data.begin(), data.end(), 0);  // Total number of 1's
    int cnt_one = 0, max_one = 0;
    int left = 0, right = 0;
    
    while (right < data.size()) {
        cnt_one += data[right++];                 // Add new element
        
        if (right - left > ones)                  // Maintain window size
            cnt_one -= data[left++];
            
        max_one = max(max_one, cnt_one);         // Update maximum 1's seen
    }
    
    return ones - max_one;                        // Minimum swaps needed
}
                

Explanation:

• **Window Management**:
  • Window size equals total number of 1's
  • Slide window through array
  • Track 1's count in current window
• **Counting Logic**:
  • Add new elements to window
  • Remove elements when window too large
  • Update maximum 1's seen in any window
• **Swap Calculation**:
  • Best case: All 1's already together
  • Worst case: No 1's together
  • Required swaps is difference between total and maximum