Minimum Swaps to Group All 1s Together II — Circular Fixed Window (LC 1151)

Problem Statement#

LeetCode 1151 — Minimum Swaps to Group All 1s Together II (Medium)

You are given a circular binary array nums. A swap exchanges two positions. Return the minimum number of swaps needed to group all 1s together in any contiguous subarray. The array is circular: nums[n-1] and nums[0] are adjacent.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is 0 or 1

Input:  nums = [0, 1, 0, 1, 1, 0, 0]
Output: 1

Input:  nums = [0, 1, 1, 1, 0, 0, 1, 1, 0]
Output: 2

Why This Problem Matters#

This is the standard circular fixed-size sliding window problem. It tests whether you recognize that: (1) the answer window has a fixed size — the total count of 1s; (2) circularity can be handled with modulo indexing; (3) minimizing swaps is equivalent to maximizing 1s inside the window — a mental inversion that is the signature of this problem family.

Google and Amazon use this problem to distinguish candidates who know sliding window from those who truly understand when and why to apply it. The "minimize swaps" framing is a deliberate misdirection — the real work is maximizing 1s in a fixed window, a much more natural formulation.

The Core Insight#

Let k = total number of 1s in nums. Since every 1 must end up in a contiguous block of size k, the destination window has exactly k slots. For a given window, the number of 0s inside it equals the swaps needed (each 0 must swap with a 1 from outside).

Minimize swaps = maximize 1s in any window of size k.

For circularity: use modulo indexing. Slide a window of size k using nums[i % n] to wrap around. Space is O(1) — no extra array needed.

Visual Dry Run#

Input: nums = [0,1,0,1,1,0,0], k = 3 (three 1s)

Max 1s = 2 → min swaps = 3 - 2 = 1

Solution (Optimal)#

def minSwaps(nums: list[int]) -> int:
    k = sum(nums)
    if k == 0 or k == len(nums):
        return 0
 
    n = len(nums)
    ones_in_window = sum(nums[:k])
    max_ones = ones_in_window
 
    for i in range(k, n + k):
        ones_in_window += nums[i % n]
        ones_in_window -= nums[(i - k) % n]
        max_ones = max(max_ones, ones_in_window)
 
    return k - max_ones

var minSwaps = function(nums) {
    const n = nums.length;
    let k = 0;
    for (const num of nums) k += num;
 
    if (k === 0 || k === n) return 0;
 
    let onesInWindow = 0;
    for (let i = 0; i < k; i++) onesInWindow += nums[i];
 
    let maxOnes = onesInWindow;
 
    for (let i = k; i < n + k; i++) {
        onesInWindow += nums[i % n];
        onesInWindow -= nums[(i - k) % n];
        maxOnes = Math.max(maxOnes, onesInWindow);
    }
 
    return k - maxOnes;
};

Time: O(n) — one pass to count 1s, one pass to slide the window Space: O(1) — modulo indexing avoids creating a doubled array

Common Mistakes#

• Not treating the array as circular — missing wrap-around windows gives wrong answers on inputs where the optimal group spans the boundary
• Setting window size to n instead of k — the window represents where the 1s will live, so size must equal the count of 1s
• Not handling k == 0 or k == n early — zero 1s or all 1s need zero swaps; sliding logic still works but early return is cleaner
• Checking ones_in_window before completing the shrink — count must be stable before updating max
• Off-by-one in loop bound: loop runs from k to n + k - 1 (n iterations), giving all n possible circular window positions

Interview Tips#

• State the inversion immediately: "Minimize swaps equals maximize 1s in a window of size k"
• Explain why the window size is exactly k (total 1s), not n
• Modulo indexing is cleaner than doubling: nums[i % n] naturally wraps around
• Handle edge cases k == 0 and k == n upfront to show thoroughness

Follow-up Questions#

• Linear version (no circularity): slide only n - k + 1 windows — no modulo needed; otherwise identical
• Group all 0s instead: count total 0s as window size m; maximize 0s in any window of size m
• Find the actual swap positions: after finding the optimal window, collect 0s inside and 1s outside — those are the swap pairs
• Multiple target values: count occurrences of the target value; use same fixed-window approach

Key Takeaways#

• Minimize swaps to group all 1s = maximize 1s inside a fixed window of size k (total count of 1s)
• Handle circularity with modulo indexing nums[i % n] — no need to physically double the array
• Loop runs n iterations: from index k to n + k - 1, covering every possible circular window starting position
• Edge cases k == 0 and k == n return 0 immediately — the array is already grouped
• Time O(n), space O(1) — this is the optimal in-place circular sliding window pattern