Minimum Swaps to Group All 1's Together II

Medium
801.

Minimum Swaps to Group All 1's Together II

Minimum Swaps to Group All 1's Together II is a medium coding problem on arrays and sliding window, asked in Amazon, Google, Arcesium and Walmart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minSwaps = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Minimum Swaps to Group All 1's Together II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Swaps to Group All 1's Together II is a medium coding problem on arrays and sliding window, asked in Amazon, Google, Arcesium and Walmart interviews.

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

Hints for Minimum Swaps to Group All 1's Together II

  1. Hint 1

    The final block has exactly as many slots as there are 1s — call that w.

  2. Hint 2

    Each 0 inside the chosen block costs one swap, because a 1 outside must come in to replace it.

  3. Hint 3

    So slide a circular window of width w and maximise the 1s inside it.

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

Java

public static int minSwaps(int[] nums) {
    int n = nums.length, w = 0;
    for (int x : nums) w += x;
    if (w == 0 || w == n) return 0;
    int ones = 0;
    for (int i = 0; i < w; i++) ones += nums[i];
    int best = ones;
    for (int i = 1; i < n; i++) {
        ones -= nums[i - 1];
        ones += nums[(i + w - 1) % n];
        best = Math.max(best, ones);
    }
    return w - best;
}

C++

int minSwaps(vector<int>& nums) {
    int n = (int) nums.size(), w = 0;
    for (int x : nums) w += x;
    if (w == 0 || w == n) return 0;
    int ones = 0;
    for (int i = 0; i < w; i++) ones += nums[i];
    int best = ones;
    for (int i = 1; i < n; i++) {
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sliding Window Technique