1151. Minimum Swaps to Group All 1's Together

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 <= data.length <= 105

• data[i] is 0 or 1.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

  • Link 1

  • Link 2

Examples

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 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].

Example 4

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

Output: 8

Solutions

Solution 1

/**
 * Time complexity : O(n), when n is the length of the array.
 * Space complexity : O(1)
 */

class Solution {
    public int minSwaps(int[] data) {
        if(data == null || data.length <= 2) {
            return 0;
        }
        
        int numOf1 = 0;
        for(int i = 0; i < data.length; i++) {
            if(data[i] == 1) {
                numOf1++;
            }
        }
        
        int currOne = 0;
        for(int i = 0; i < numOf1; i++) {
            if(data[i] == 1) {
                currOne++;
            }
        }
        
        int result = numOf1-currOne;
        
        for(int i = 1; i <= data.length-numOf1; i++) {
            if(data[i-1] == 1) {
                currOne--;
            }
            if(data[i + numOf1 - 1] == 1) {
                currOne++;
            }
            result = Math.min(result, numOf1-currOne);
        }
        
        
        return result;
    }
}

Solution 2

/**
 * Time complexity : O(n), when n is the length of the array.
 * Space complexity : O(1)
 */
 
 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;

        while (right < data.length) {
            // updating the number of 1's by adding the new element
            cnt_one += data[right++];
            // maintain the length of the window to ones
            if (right - left > ones) {
                // updating the number of 1's by removing the oldest element
                cnt_one -= data[left++];
            }
            // record the maximum number of 1's in the window
            max_one = Math.max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

Follow up