Minimum Swaps to Group all ones together

XXX. Minimum Swaps to Group All 1's

Array

Sliding Window

<div class="section">
    <h2>Problem Statement:</h2>
    <p>
        Given a binary array data, return the minimum number of swaps required to group all 1's together in a contiguous subarray.
    </p>
    <ul>
        <li>Array contains only 0s and 1s</li>
        <li>All 1's must be adjacent after swaps</li>
        <li>Only adjacent swaps are allowed</li>
    </ul>
</div>

<div class="section">
    <h2>Algorithm:</h2>
    <ol class="algorithm-steps">
        <li>
            **Key Insight**:
            <ul>
                <li>Final array must have all 1's together</li>
                <li>Window size equals total number of 1's</li>
                <li>Required swaps = Total 1's - Max 1's in window</li>
            </ul>
        </li>
        <li>
            **Sliding Window**:
            <ul>
                <li>Maintain fixed-size window</li>
                <li>Count 1's in current window</li>
                <li>Track maximum 1's seen in any window</li>
            </ul>
        </li>
    </ol>
</div>

<div class="section">
    <h2>Complexity:</h2>
    <p>
        <strong>Time Complexity:</strong> O(n), one pass through array
        <br>
        <strong>Space Complexity:</strong> O(1), constant extra space
    </p>
</div>

<div class="section">
    <h2>Implementation:</h2>

    <h3>Java Solution:</h3>
    <div class="code-block">
        <div class="code-content">
            <pre><code class="language-java">

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

}

<h3>Python Solution:</h3>
    <div class="code-block">
        <div class="code-content">
            <pre><code class="language-python">

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
            </code></pre>
        </div>
    </div>

    <h3>C++ Solution:</h3>
    <div class="code-block">
        <div class="code-content">
            <pre><code class="language-cpp">

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

}

<div class="section">
    <h2>Explanation:</h2>
    <ul>
        <li>
            **Window Management**:
            <ul>
                <li>Window size equals total number of 1's</li>
                <li>Slide window through array</li>
                <li>Track 1's count in current window</li>
            </ul>
        </li>
        <li>
            **Counting Logic**:
            <ul>
                <li>Add new elements to window</li>
                <li>Remove elements when window too large</li>
                <li>Update maximum 1's seen in any window</li>
            </ul>
        </li>
        <li>
            **Swap Calculation**:
            <ul>
                <li>Best case: All 1's already together</li>
                <li>Worst case: No 1's together</li>
                <li>Required swaps is difference between total and maximum</li>
            </ul>
        </li>
    </ul>
</div>