Minimum Swaps to Group All 1s Together II [Medium] — Fixed Window

Problem Statement

A circular binary array means you can rotate it. With a single swap you can move a 0 to a 1 and vice versa. Return the minimum number of swaps to group all 1s together in a contiguous subarray.

Input: [0,1,0,1,1,0,0] → Output: 1

Intuition

Count total 1s = window size k. A fixed window of size k is valid when it contains the most 1s — minimum swaps = k - (1s in window). Try all rotations (double the array or handle circular with modulo).

Solutions

Python

def minSwaps(nums: list[int]) -> int:
    k = sum(nums)
    if k == 0 or k == len(nums): return 0
    n = len(nums)
    # circular: use double array
    arr = nums + nums
    ones_in_window = sum(arr[:k])
    max_ones = ones_in_window
    for i in range(k, 2*n):
        ones_in_window += arr[i] - arr[i-k]
        max_ones = max(max_ones, ones_in_window)
    return k - max_ones

C++

int minSwaps(vector<int>& nums) {
    int k=0; for(int n:nums)k+=n;
    if(!k) return 0;
    int n=nums.size(), win=0, ans;
    for(int i=0;i<k;i++) win+=nums[i];
    ans=k-win;
    for(int i=k;i<2*n;i++){
        win+=nums[i%n]-nums[(i-k+n)%n];
        ans=min(ans,k-win);
    }
    return ans;
}

Complexity

Time: O(n), Space: O(1)