Minimum Number of swaps required to group all ones together in array of 0s and 1s

Question

Problem Statement:

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.

Example 1:

Input: [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: [0,0,0,1,0]

Output: 0

Explanation:

Since there is only one 1 in the array, no swaps needed.

Example 3:

Input: [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].

This is my solution. I used sliding window.

First I counted total number of ones in the given array.

To group the 1s in minimum number of swaps we have to group them up in a cluster where their density is already more.

So I made an array which keeps a count of 1s encountered till that element

Then I created a window of the size of total 1s in that array and moved that window till the end to find which sub array had maximum number of 1s, because this is the area where we will insert other 1s

The code is as follows

int minSwaps(vector<int>& data) {
        // Size of given array
        int size = data.size();

        // Total ones in given array
        int totalOnes = 0;

        // Counting total ones in array
        for(int i = 0 ; i < size;++i){
            if(data[i]==1) totalOnes++;
        }

        if(totalOnes==size) return 0;
        if(totalOnes==0) return 0;

        // Using a winow of the size of total ones
        int window = totalOnes;

        // maxOnes will store the value of maximum ones in any sliding window of size 'window'
        int maxOnes = INT_MIN;

        // This array will store total number of ones till index i
        vector<int> onesTillNow(size,0);

        if(data[0]==1)
            onesTillNow[0]=1;
        else
            onesTillNow[0]=0;

        for(int i = 1; i < size;++i){
            if(data[i]==1)
                onesTillNow[i] = onesTillNow[i-1] + 1;
            else
                onesTillNow[i] = onesTillNow[i-1];
        }

        for(int i = window - 1; i < size ; ++i){
            if(i == window - 1 )
                totalOnes = onesTillNow[i];
            else
                totalOnes = onesTillNow[i] - onesTillNow[i-window];

            if(totalOnes > maxOnes) maxOnes = totalOnes;
        }
        return window - maxOnes;
    }

Can you suggest any improvements to this or a better way to do it?

G. Sliepen · Accepted Answer · 2019-08-12 10:17:09Z

The algorithm is sound, and it's O(N). There are only two things I see you can improve.

Make use of the standard library

The C++ library comes with a lot of functions, including ones that can take care of summing elements of a vector for you. So to find the number of ones in the input vector, you can just write:

#include <algorithm>
...
int window = std::accumulate(std::begin(data), std::end(data), 0);

You don't need `onesTillNow`

When moving your window over the input array, you don't need to store all the number of ones for every window position. You just want to know the maximum number of ones in a window. If you just have a single variable int onesInWindow, and initialize it with the sum of ones in the first window:

int onesInWindow = std::accumulate(std::begin(data), std::begin(data) + window, 0);
int maxOnes = onesInWindow;

Then you can iterate over all the other window positions like this:

for(int i = window; i < size; i++) {
    onesInWindow -= data[i - window];
    onesInWindow += data[i];
    maxOnes = std::max(maxOnes, onesInWindow);  
}

Toby Speight · Accepted Answer · 2019-08-12 09:58:13Z

We have no need to modify data - it should be a reference to const, so the caller can be guaranteed that we won't change the contents.

It appears that you have a using std::vector hidden somewhere - you should really show this as part of your review request. It's generally best to keep such things out of the global namespace - use it only within the scope of a function.

None of your unit tests are shown in the review, so it's impossible to know if they are sufficiently complete (or, indeed, whether there are redundant tests).

Stack Exchange Network

Minimum Number of swaps required to group all ones together in array of 0s and 1s

2 Answers 2

Make use of the standard library

You don't need `onesTillNow`

You must log in to answer this question.

Hot Network Questions

Minimum Number of swaps required to group all ones together in array of 0s and 1s

2 Answers 2

Make use of the standard library

You don't need onesTillNow

You must log in to answer this question.

Related

Hot Network Questions

You don't need `onesTillNow`