Minimum Swaps to Group All 1's Together II

This is the most optimal approach. It builds upon the sliding window idea but avoids the O(N) space complexity of creating a doubled array. The circularity of the array is handled elegantly and efficiently by using the modulo operator (%) for calculating indices that would otherwise wrap around.

• Calculate totalOnes, the total count of 1s in nums.
• If totalOnes is 0 or n, return 0.
• Calculate the number of 1s in the first window of size totalOnes (indices 0 to totalOnes - 1). Let this be currentOnes.
• Initialize maxOnes = currentOnes.
• Iterate i from 1 to n - 1. This i represents the starting index of the sliding window.
• The element leaving the window is at index i - 1.
• The element entering the window is at index i + totalOnes - 1. To handle the wrap-around, we calculate the actual index as (i + totalOnes - 1) % n.
• Update currentOnes in O(1) by subtracting nums[i - 1] and adding nums[(i + totalOnes - 1) % n].
• Update maxOnes = max(maxOnes, currentOnes).
• After iterating through all n possible starting positions, return totalOnes - maxOnes.

This approach refines the sliding window technique to achieve optimal space complexity. Instead of physically creating a doubled array, we simulate the behavior of a circular window on the original array.

1. As before, we first count totalOnes to determine the window size.
2. We compute the number of 1s in the initial window, which spans from index 0 to totalOnes - 1. This gives us our initial currentOnes and maxOnes.
3. We then slide the window n-1 more times to cover all possible circular starting positions. The loop for the window's start index i runs from 1 to n-1.
4. In each iteration, we update currentOnes. The element leaving the window is at index i - 1. The element entering the window would be at index i + totalOnes - 1 in a linear array. To handle the circularity, we find its actual index using the modulo operator: (i + totalOnes - 1) % n.
5. The update rule is: currentOnes = currentOnes - nums[i - 1] + nums[(i + totalOnes - 1) % n].
6. We keep track of the maximum currentOnes seen in maxOnes.
7. Finally, the minimum number of swaps is totalOnes - maxOnes, which represents the minimum number of 0s in any possible window.

This method provides the same linear time efficiency as the doubled array approach but with the significant advantage of constant space usage.

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int totalOnes = 0;
        for (int x : nums) {
            totalOnes += x;
        }

        if (totalOnes == 0 || totalOnes == n) {
            return 0;
        }

        int currentOnes = 0;
        // Calculate ones in the first window (from 0 to totalOnes-1)
        for (int i = 0; i < totalOnes; i++) {
            currentOnes += nums[i];
        }

        int maxOnes = currentOnes;
        // Slide the window and handle wrap-around with modulo
        for (int i = 1; i < n; i++) {
            // Element leaving is at i-1
            int leavingElement = nums[i - 1];
            // Element entering is at (i + totalOnes - 1) % n
            int enteringElement = nums[(i + totalOnes - 1) % n];
            
            currentOnes = currentOnes - leavingElement + enteringElement;
            maxOnes = Math.max(maxOnes, currentOnes);
        }

        return totalOnes - maxOnes;
    }
}