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

Time: O(n)

Space: O(1)

Intuition

Find minimum swaps to group all 1s. Sliding window of size = count(1s). Find window with maximum 1s; minimum swaps = window_size - max_ones_in_window.

Algorithm

1Count total ones = k. Sliding window of size k.
2Max ones in any window of size k using circular array (treat as doubled).
3Answer = k - max_ones_in_window.

Common Pitfalls

•Circular array: use doubled array or modular indexing. Window size = count of 1s in original array.

2134.cs

// Approach: Sliding window of size k (count of 1s) on circular array; minimize zeros inside.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinSwaps(int[] nums)
    {
        int n = nums.Length;
        int k = nums.Where(x => x == 1).Count();
        int ones = 0, maxOnes = 0;

        for (int i = 0; i < n * 2; i++)
        {
            if (i >= k && nums[(i - k) % n] == 1)
                --ones;
            if (nums[i % n] == 1)
                ++ones;
            maxOnes = Math.Max(maxOnes, ones);
        }

        return k - maxOnes;
    }
}

Was this solution helpful?