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

Problem

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.

Example 2:

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

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

  Constraints:

• 1 <= nums.length <= 10^5

• nums[i] is either 0 or 1.

Solution (Java)

class Solution {
    public int minSwaps(int[] nums) {
        int l = nums.length;
        int[] ones = new int[l];
        ones[0] = nums[0] == 1 ? 1 : 0;
        for (int i = 1; i < l; i++) {
            if (nums[i] == 1) {
                ones[i] = ones[i - 1] + 1;
            } else {
                ones[i] = ones[i - 1];
            }
        }
        if (ones[l - 1] == l || ones[l - 1] == 0) {
            return 0;
        }
        int ws = ones[l - 1];
        int minSwaps = Integer.MAX_VALUE;
        int si = 0;
        int ei;
        while (si < nums.length) {
            ei = (si + ws - 1) % l;
            int totalones;
            if (ei >= si) {
                totalones = ones[ei] - (si == 0 ? 0 : ones[si - 1]);
            } else {
                totalones = ones[ei] + (ones[l - 1] - ones[si - 1]);
            }
            int swapsreq = ws - totalones;
            if (swapsreq < minSwaps) {
                minSwaps = swapsreq;
            }
            si++;
        }
        return minSwaps;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).