Leetcode: Minimum Swaps to Group 1's Together

This question is asked at IBM, Twitter, and Expedia. Here it is:

Given the 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. 

Here's the example:

Input: data = [1, 0, 1, 0, 1]

Output: 1

There are 3 ways to group all 1's together:

[1, 1, 1, 0, 0]

[0, 1, 1, 1, 0]

[0, 0, 1, 1, 1]

The minimum is 1. 

Thinking about it, the final result we want is a window with a length n (the total number of 1s). 

We check all of the windows with the same length n, and we find the maximum.

Assuming that there are ones 1's in the input array we need to fund a subarray of 1's and put every 1

s in it by swapping the 0's out and find the maximum number of 1's in the window so that we can make the smallest number of swaps. 

We use 2 pointers, left and right, to maintain a sliding window of length ones, and while we check every window through the input array data and we want the maximum number of ones. We want to maintain the window length as it slides through data. 

class Solution {

    public int minSwaps(int[] data) {

        int ones = Arrays.stream(data).sum();

        int cnt_one = 0, max_one = 0;

        int left = 0, right = 0;

        //sliding window, make sure the length is equal to number of 1's

        while(right < data.length) {

            cnt_one += data[right++];

            if(right - left > ones) {

                cnt_one -= data[left];

                left++;

            }

            //maximum number of ones.

            max_one = Math.max(max_one, cnt_one);

        }

        //remaining ones to switch

        return ones - max_one;

    }

}