⚡Flashcard Drill➔
NeetCode #778LC-2134MediumGreedy
← Back to All Problems

#778 · #2134 · Minimum Swaps to Group All 1's Together II(最少交换次数来组合所有的 1 II)

📌 Problem Statement & Constraints

Given a circular binary array nums, return the minimum number of swaps to group all the 1s together at any location. Constraints: 1 <= nums.length <= 10^5, nums[i] is 0 or 1.

💡 Core Algorithmic Approaches

  1. Let k be the number of ones. The final block occupies some circular window of length k.
  2. The swaps needed to gather the ones into a window equal the number of zeros inside that window.
  3. Minimise the zero count over all circular windows of length k.
  4. Use a sliding window over the doubled array (via modular indexing) to evaluate each window in O(1).

💻 Benchmark Python3 Implementation

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        k = sum(nums)
        if k == 0:
            return 0                   # no ones to group
        n = len(nums)
        cur = sum(nums[:k])            # ones in the first window
        best = k - cur                 # zeros in that window
        for i in range(1, n):
            cur += nums[(i + k - 1) % n] - nums[i - 1]
            best = min(best, k - cur)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one sliding pass over the circular windows.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Ignoring the circular wrap: the optimal block may straddle the array boundary, which the modular window handles.
  • Forgetting the k == 0 case: k - cur is 0 anyway, but the guard avoids building windows of length 0.
  • Counting ones instead of zeros: the cost is the number of zeros in the window.
  • Trying to simulate swaps directly: that is far slower than the window count.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems