1151. Minimum Swaps to Group All 1's Together
Last updated
Last updated
/**
* 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;
}
}