Minimum Swaps to Group All 1's Together

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.

Constraints

• $1 \leq$ data.length $ \leq 10^5$
• data[i] is either 0 or 1.

Solution

This problem asks us to return minimum number of swaps, which means that we do not need to take real swap actions for given array. And we can find that the value in this array is either 0 or 1 within the constraints, so we could keep a sliding window of the length that is equal to the number of 1 in the array.

$Len_{window} = Num_{1}$

In this way, for those positions of value 0, which means that we could swap them with 1, so this problems turns to that we need to find a sliding window with minimum number of 0.

We can set two pointers of left and right boundary to control this sliding window.

Code

class Solution {
public:
    int minSwaps(vector<int>& data) {
        int ones = 0, len = data.size();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;
        for(int num:data) // get the sum of the number of 1
            ones += num;
        while(right < n){
            cnt_one += data[right++];
            if(right - left > ones){ // maintain the length of the window to ones
                cnt_one -= data[left++];
            }
            max_one = max(max_one, cnt_one);
        }
        return ones - max_one;
    }
};

The problem is cited from Leetcode 1151. Minimum Swaps to Group All 1’s Together. And the solution is cited from LeetCode Official Solution Approach 1: Sliding Window with Two Pointers.