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?
2 Answers 2
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);
}
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).