Problem Informations

• Problem Index: 1151
• Problem Link: Minimum Swaps to Group All 1’s Together
• Topics: Array, Sliding Window

Problem Description

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.

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1’s together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: Since there is only one 1 in the array, no swaps are needed.

Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Constraints:

1 <= data.length <= 10^5
data[i] is either 0 or 1.

Intuition

The problem requires us to group all 1’s in a binary array together with the minimum number of swaps. To accomplish this, we need a strategy that efficiently calculates the number of swaps necessary to consolidate all 1’s. The key observation is to use a sliding window, whose size is equal to the total number of 1’s in the array. This window will allow us to slide through the array and count the number of 1’s present at each position of the window, thus enabling us to compute the number of swaps needed to maximize the count of 1’s within this window.

Approach

1. Calculate the total number of 1’s in the entire array using the accumulate function. This value will be used to establish the size of the sliding window.

2. Initialize the sliding window by calculating the number of 1’s in the first subarray whose size equals the total number of 1’s. This initial count of 1’s in the window is achieved by summing up the initial portion of the array.

3. Compute the initial minimum number of swaps necessary by subtracting the number of 1’s in this initial window from the total number of 1’s. This result represents the swaps needed to achieve a perfect window containing all 1’s at this starting position.

4. Slide the window across the array from left to right. For each new window position, update the count of 1’s by subtracting the first element of the previous window and adding the next element in the sequence. This step efficiently transitions the window one position to the right.

5. For each window position, calculate the number of swaps needed by subtracting the current count of 1’s in the window from the total count of 1’s. Update the minimum number of swaps if a smaller value is found.

6. Continue the sliding window process until the end of the array is reached, and return the minimum number of swaps recorded.

Using this approach, we achieve an efficient $O(n)$ complexity by managing and updating the sliding window counts without revisiting the elements multiple times, ensuring optimal performance even for large arrays.

Code

C++

class Solution {
public:
    int minSwaps(vector<int>& data) {

        // Count the total number of 1's in the array.
        int totalOnes = accumulate(data.begin(), data.end(), 0);

        // Calculate how many 1's are in the first window of size `totalOnes`.
        int currentOnesInWindow = accumulate(data.begin(), data.begin() + totalOnes, 0);

        // Find the minimum number of swaps required to group all 1's together by calculating the difference.
        int minSwapsNeeded = totalOnes - currentOnesInWindow;

        // Use sliding window technique to find the minimum swaps required by checking each window.
        for (int i = 0; i < data.size() - totalOnes; i++) {
            // Update the current window count by subtracting the element that goes out and adding the new element.
            currentOnesInWindow += data[totalOnes + i] - data[i];

            // Calculate the swaps needed for the current window and update the minimum swaps if necessary.
            minSwapsNeeded = min(minSwapsNeeded, totalOnes - currentOnesInWindow);
        }

        return minSwapsNeeded;
    }
};

Python

class Solution:
    def minSwaps(self, data):

        # Count the total number of 1's in the array.
        totalOnes = sum(data)

        # Calculate how many 1's are in the first window of size `totalOnes`.
        currentOnesInWindow = sum(data[:totalOnes])

        # Find the minimum number of swaps required to group all 1's together by calculating the difference.
        minSwapsNeeded = totalOnes - currentOnesInWindow

        # Use sliding window technique to find the minimum swaps required by checking each window.
        for i in range(len(data) - totalOnes):
            # Update the current window count by subtracting the element that goes out and adding the new element.
            currentOnesInWindow += data[totalOnes + i] - data[i]

            # Calculate the swaps needed for the current window and update the minimum swaps if necessary.
            minSwapsNeeded = min(minSwapsNeeded, totalOnes - currentOnesInWindow)

        return minSwapsNeeded

Complexity

• Time complexity: $O(n)$

  The time complexity is $O(n)$ because the algorithm consists of two main loops that both iterate over the entire array data. The first call to accumulate on data to count the total number of 1’s takes $O(n)$ time. The second call to accumulate initializes the count of 1’s in the first window, which takes $O(k)$ time, where $k$ is the number of 1’s (less than or equal to $n$). Lastly, the for loop iterates through the remaining elements of the array, updating the sliding window, and this loop runs for $O(n-k)$ times, collectively maintaining an $O(n)$ complexity. Thus, the total time complexity is $O(n)$.

• Space complexity: $O(1)$

  The space complexity is $O(1)$ because the algorithm uses a constant amount of extra space, independent of the input size. Variables like totalOnes, currentOnesInWindow, and minSwapsNeeded are all scalar values storing integers, and no additional data structures are required that scale with the size of the input array. Hence, the space complexity is constant, $O(1)$.