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

Examples

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.

Solutions

/**
 * 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;
    }
}

/**
 * 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

Previous1143. Longest Common Subsequence Next1165. Single-Row Keyboard

Last updated 4 years ago

Was this helpful?