2134. Minimum Swaps to Group All 1's Together II

 

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.

 

Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.

class Solution {

public int minSwaps(int[] nums) {

int minValue = Integer.MAX_VALUE;

int totOnes = 0;

for(int num: nums){

totOnes+=num;

}

int oneCount = nums[0];

int end = 0;

for(int start = 0;start<nums.length;++start){

if(start != 0){

oneCount -= nums[start - 1];

}

while(end - start +1 < totOnes){

end++;

oneCount += nums[end % nums.length];

}

minValue = Math.min(minValue,totOnes - oneCount);

}

return minValue;

}

}

 

Given an array of 0's and 1's, we need to write a program to find the minimum number of swaps required to group all 1's present in the array together.

Examples: Input: arr[] = [1, 0, 1, 0, 1]
Output: 1
Explanation: Only 1 swap is required to group all 1's together. Swapping index 1 with 4 will
give arr[] = [1, 1, 1, 0, 0]

Input: arr[] = [1, 1, 0, 1, 0, 1, 1]
Output: 2
Explanation: Only 2 swap is required to group all 1's together. Swapping index 0 with 2 and
1 with 4 will give arr[] = [0, 0, 1, 1, 1, 1, 1]

Input: arr[] = [0, 0, 0]
Output: -1
Explanation: No 1s are present in the array, so return -1.

non circular array based code 

class gfg{

    public int minSwaps(int[] nums){

        int totOne = 0

        for(int num : nums){

                totOne += num;

        }

        int countOne = 0;

        int maxOne = 0;

        for(int i = 0 ; i<nums.length;i++){

            conntOne += nums[i];

            if(i<=totOne){

                    countOne -= nums[i - totOne];

            }

            if(i<=totOne - 1){

                    maxOne = Math.max(maxOne,countOne);

            }

        }

        return totOne - maxOne

    }

}