{x}
blog image

Minimum Swaps to Group All 1's Together

Solution Explanation: Minimum Swaps to Group All 1's Together

This problem asks for the minimum number of swaps needed to group all the 1s in a binary array together. The optimal solution uses a sliding window approach.

Algorithm:

  1. Count 1s: First, count the total number of 1s in the array. Let's call this count k. This represents the size of the window we'll use to group the 1s.

  2. Initial Window: Create a sliding window of size k. Calculate the number of 1s within this initial window. Let's call this currentOnes.

  3. Sliding Window: Slide the window one element at a time to the right. For each slide:

    • Subtract the value of the element leaving the window from currentOnes.
    • Add the value of the element entering the window to currentOnes.
    • Update the maximum number of 1s encountered in a window (maxOnes).

  4. Minimum Swaps: The minimum number of swaps needed is k - maxOnes. This is because maxOnes represents the maximum number of 1s that can be grouped together without any swaps, and we need to move k - maxOnes ones to achieve the optimal grouping.

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once to count 1s and then again to slide the window.

Space Complexity: O(1). We use only a few constant extra variables.

Code Examples:

The following code examples demonstrate the sliding window approach in several programming languages:

Python:

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        k = sum(data)  # Count of 1s
        currentOnes = sum(data[:k]) # Ones in initial window
        maxOnes = currentOnes
        for i in range(k, len(data)):
            currentOnes += data[i] - data[i - k] # Slide the window
            maxOnes = max(maxOnes, currentOnes)
        return k - maxOnes

Java:

class Solution {
    public int minSwaps(int[] data) {
        int k = 0;
        for (int x : data) k += x;
        int currentOnes = 0;
        for (int i = 0; i < k; ++i) currentOnes += data[i];
        int maxOnes = currentOnes;
        for (int i = k; i < data.length; ++i) {
            currentOnes += data[i] - data[i - k];
            maxOnes = Math.max(maxOnes, currentOnes);
        }
        return k - maxOnes;
    }
}

C++:

class Solution {
public:
    int minSwaps(vector<int>& data) {
        int k = accumulate(data.begin(), data.end(), 0);
        int currentOnes = accumulate(data.begin(), data.begin() + k, 0);
        int maxOnes = currentOnes;
        for (int i = k; i < data.size(); ++i) {
            currentOnes += data[i] - data[i - k];
            maxOnes = max(maxOnes, currentOnes);
        }
        return k - maxOnes;
    }
};

JavaScript:

const minSwaps = (data) => {
    const k = data.reduce((sum, x) => sum + x, 0);
    let currentOnes = data.slice(0, k).reduce((sum, x) => sum + x, 0);
    let maxOnes = currentOnes;
    for (let i = k; i < data.length; ++i) {
        currentOnes += data[i] - data[i - k];
        maxOnes = Math.max(maxOnes, currentOnes);
    }
    return k - maxOnes;
};

These examples all follow the same core logic, adapting the syntax to their respective languages. They all achieve the optimal time and space complexity.