LeetCode 2134 - Minimum Swaps to Group All 1's Together II

The problem is asking us to find the minimum number of swaps required to group all 1s in a binary circular array together at any contiguous segment. The array is circular, which means the end of the array wraps around to the beginning.

leetcodemediumarraysliding-window

LeetCode Problem 2134

Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem is asking us to find the minimum number of swaps required to group all 1s in a binary circular array together at any contiguous segment. The array is circular, which means the end of the array wraps around to the beginning. Each swap can only exchange the values of two distinct positions in the array. The input is a binary array, meaning every element is either 0 or 1. The expected output is a single integer representing the minimum number of swaps needed.

Constraints tell us that the array can be large, up to 10^5 elements, which makes a naive approach that checks every possible grouping infeasible. We also know that the array may already have all 1s grouped or may require the circular property to minimize swaps. Important edge cases include arrays where all elements are 1s or 0s, arrays with alternating 0s and 1s, and arrays where the minimal grouping occurs across the boundary between the last and first element.

Approaches

Brute Force

A brute-force approach would consider every possible contiguous subarray of length equal to the total number of 1s in the array and calculate how many 0s are in that segment. Each 0 represents a needed swap to bring a 1 into the segment. Because the array is circular, we would need to consider segments that wrap around from the end to the beginning. This approach works correctly but is inefficient, because for an array of length n and k ones, we would examine n subarrays and count 0s in each subarray in O(k) time, resulting in O(n*k) time complexity, which is too slow for large arrays.

Optimal Approach

The key insight is that the minimum number of swaps is equal to the minimum number of 0s in any contiguous subarray of length equal to the total number of 1s. To handle the circular property efficiently, we can duplicate the array (concatenate it to itself) and apply a sliding window of length equal to the number of 1s. This way, every circular segment is represented as a standard linear segment in the doubled array. Using a sliding window, we can maintain a running count of 0s and efficiently determine the minimum count across all windows.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*k) O(1) Examine all subarrays of length k and count 0s
Optimal O(n) O(n) Duplicate array and use sliding window to track 0s

Algorithm Walkthrough

  1. Count the total number of 1s in the array and store it as numOnes.
  2. If numOnes is 0 or equal to the array length, return 0 immediately because no swaps are needed.
  3. Duplicate the array by concatenating it to itself, creating numsExtended.
  4. Initialize a sliding window of length numOnes and count the number of 0s in the first window. Store this count as minZeros.
  5. Slide the window across numsExtended from index 1 to len(nums). For each step, remove the effect of the element leaving the window and add the effect of the element entering the window:
  • If the outgoing element is 0, decrease the zero count.
  • If the incoming element is 0, increase the zero count.
  • Update minZeros if the current zero count is smaller.
  1. After sliding through all possible windows, minZeros will represent the minimum number of swaps needed.
  2. Return minZeros.

Why it works: The algorithm relies on the invariant that the minimum number of 0s in any window of size equal to the total number of 1s corresponds exactly to the minimum swaps required. Duplicating the array allows us to handle circular subarrays as linear ones without special cases.

Python Solution

from typing import List

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        numOnes = sum(nums)
        if numOnes <= 1:
            return 0
        
        n = len(nums)
        numsExtended = nums + nums
        currentZeros = numsExtended[:numOnes].count(0)
        minZeros = currentZeros
        
        for i in range(1, n):
            if numsExtended[i - 1] == 0:
                currentZeros -= 1
            if numsExtended[i + numOnes - 1] == 0:
                currentZeros += 1
            minZeros = min(minZeros, currentZeros)
        
        return minZeros

The implementation first counts all 1s to determine the window size. By extending the array, we can apply a sliding window without special circular logic. The zero count in each window directly maps to the swaps required to group all 1s, and we track the minimum across all possible windows.

Go Solution

func minSwaps(nums []int) int {
    numOnes := 0
    for _, v := range nums {
        if v == 1 {
            numOnes++
        }
    }
    if numOnes <= 1 {
        return 0
    }
    
    n := len(nums)
    numsExtended := append(nums, nums...)
    
    currentZeros := 0
    for i := 0; i < numOnes; i++ {
        if numsExtended[i] == 0 {
            currentZeros++
        }
    }
    minZeros := currentZeros
    
    for i := 1; i < n; i++ {
        if numsExtended[i-1] == 0 {
            currentZeros--
        }
        if numsExtended[i+numOnes-1] == 0 {
            currentZeros++
        }
        if currentZeros < minZeros {
            minZeros = currentZeros
        }
    }
    
    return minZeros
}

The Go solution follows the same logic. Go requires explicit handling of slices and does not have a built-in count function, so we count zeros manually. The sliding window logic remains identical.

Worked Examples

Example 1: [0,1,0,1,1,0,0]

numOnes = 3, window size = 3.

Window start Window elements Zero count MinZeros
0 [0,1,0] 2 2
1 [1,0,1] 1 1
2 [0,1,1] 1 1
3 [1,1,0] 1 1
4 [1,0,0] 2 1
5 [0,0,0] 3 1
6 [0,0,1] 2 1

Output: 1

Example 2: [0,1,1,1,0,0,1,1,0]

numOnes = 5, window size = 5.

Window start Window elements Zero count MinZeros
0 [0,1,1,1,0] 2 2
1 [1,1,1,0,0] 2 2
2 [1,1,0,0,1] 2 2
3 [1,0,0,1,1] 2 2
4 [0,0,1,1,0] 3 2
5 [0,1,1,0,0] 3 2
6 [1,1,0,0,0] 3 2
7 [1,0,0,0,1] 3 2
8 [0,0,0,1,1] 3 2

Output: 2

Example 3: [1,1,0,0,1]

numOnes = 3, window size = 3.

Window start Window elements Zero count MinZeros
0 [1,1,0] 1 1
1 [1,0,0] 2 1
2 [0,0,1] 2 1
3 [0,1,1] 1 1
4 [1,1,1] 0 0

Output: 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Counting ones and sliding window each iterate over at most 2n elements
Space O(n) Doubling the array for circular handling

The time complexity is linear because each element is processed a constant number of times. The space complexity is linear due to the duplicated array.

Test Cases

# provided examples
assert Solution().minSwaps([0,1,0,1,1,0,0]) == 1
assert Solution().minSwaps([0,1,1,