Minimum Swaps to Group All 1's Together II — Medium Problem & Solution

Problem statement

A swap exchanges the values at two distinct positions. nums is a circular binary array — the last element is adjacent to the first.

Return the minimum number of swaps needed to gather all the 1s into one contiguous block (wrapping is allowed).

Example 1

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Swapping positions 1 and 5 gathers the three 1s.

Example 2

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: The block may wrap around the end.

Example 3

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: Already grouped, wrapping from index 4 to 1.

Constraints

• 1 <= nums.length <= 100000
• nums[i] is 0 or 1

How to solve Minimum Swaps to Group All 1's Together II

Fix the shape of the answer: a circular window of width w, the number of 1s. The cost of a window is its 0 count, so maximise its 1 count instead. A rolling sum over the circle does it in one pass.

Approach

1. Count the 1s to get w; if w is 0 or n, no swaps are needed.
2. Sum the first w elements as the initial window.
3. Roll the window forward n - 1 times using nums[(i + w - 1) % n] to enter and nums[i - 1] to leave.
4. Return w - best.

Why it works

Every 0 inside the block must be exchanged with a 1 outside, and one swap fixes exactly one such pair — so the cost is precisely the 0 count. Since the block has width w, its 0 count is w minus its 1 count, and maximising the latter minimises the former.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Forgetting the wrap and only sliding over [0, n - w] misses the best block in the circular cases.
• Doubling the array works too but costs O(n) extra space — the modulo avoids it.
• An all-zero or all-one array must short-circuit, or the window width is 0 or n and the roll is degenerate.

Reference solution

Python

from typing import List

def minSwaps(nums: List[int]) -> int:
    n = len(nums)
    w = sum(nums)
    if w == 0 or w == n:
        return 0
    ones = sum(nums[:w])
    best = ones
    for i in range(1, n):
        ones -= nums[i - 1]
        ones += nums[(i + w - 1) % n]
        best = max(best, ones)
    return w - best

JavaScript

var minSwaps = function(nums) {
    var n = nums.length, w = 0, i;
    for (i = 0; i < n; i++) w += nums[i];
    if (w === 0 || w === n) return 0;
    var ones = 0;
    for (i = 0; i < w; i++) ones += nums[i];
    var best = ones;
    for (i = 1; i < n; i++) {
        ones -= nums[i - 1];
        ones += nums[(i + w - 1) % n];
        if (ones > best) best = ones;
    }
    return w - best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium