Minimum Swaps to Group All 1’s Together Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Expedia IBM Twitter
Array Sliding WindowViews 2679

Problem Statement

Minimum Swaps to Group All 1’s Together Leetcode Solution – says that 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.

Minimum Swaps to Group All 1's Together Leetcode Solution

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.

Explanation

The question states to find the minimum swaps required to arrive to a contiguous array of 1’s, in other words, a group of 1’s.
So if we take an example the array: [1,0,1,0,1] we know that we must have 3 1's grouped together to form the result. It can either be [1,1,1,0,0] or [0,0,1,1,1] but it’s still a 3 length contiguous subarray.

We first create a window of size (int ones) with (int winOnes) number of 1s in it and then slide it across the array. The concept involves finding a window with a maximum 1s (int maxOnes) present in it. The remaining 0s in this particular window would be swapped by 1s, not in the window. Hence, the result would be window size (int ones) – window with max 1s (int maxOnes)

Code

Java Solution

class Solution {
    public int minSwaps(int[] data) {
        int ones = 0;
        for (int datum : data) {
            ones += datum;
        }

        if(ones == 0 || ones == 1 || ones == data.length){
            return 0;
        }

        int winOnes = 0;

        for(int i = 0; i < ones; i++){
            winOnes += data[i];
        }

        int maxOnes = winOnes;

        for(int i = ones; i < data.length; i++){
            winOnes -= data[i - ones];
            winOnes += data[i];
            maxOnes = Math.max(maxOnes, winOnes);
        }

        return ones - maxOnes;
    }

}

C++ Solution

#include <vector>
using namespace std;

class Solution {
    
public:
    int minSwaps(vector<int>& data) {
        int countOnes = accumulate(data.begin(), data.end(), 0);
        int currentSwaps = 0;
        for (int i = 0; i < countOnes; ++i) {
            currentSwaps += (1 - data[i]);
        }

        int minSwaps = currentSwaps;
        for (int i = countOnes; i < data.size(); ++i) {
            currentSwaps += (1 - data[i]) - (1 - data[i - countOnes]);
            minSwaps = min(minSwaps, currentSwaps);
        }
        return minSwaps;
    }
};

Complexity Analysis for Minimum Swaps to Group All 1’s Together LeetCode Solution:

Time Complexity

The time complexity of the above solution is O(n).

Space Complexity

The Space Complexity of the above solution is O(1).

Translate »