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
- Let
kbe the number of ones. The final block occupies some circular window of lengthk. - The swaps needed to gather the ones into a window equal the number of zeros inside that window.
- Minimise the zero count over all circular windows of length
k. - 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 == 0case:k - curis 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.