1151 - Minimum Swaps to Group All 1's Together

Difficulty: Medium | Pattern: Sliding Window | Company tags: Amazon, Facebook

Problem Statement

Given a binary array data, return the minimum number of swaps required to group all 1s present in the array together in any place in the array.

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: 3 ones total. Window of size 3: [1,0,1] has one 0 → 1 swap needed.

Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: Only 1 one, already grouped.

Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3

Approach: Sliding Window — O(n)

Key insight: Count total 1s (k). We need to find a window of size k with the maximum number of 1s. The answer is k - max_ones_in_window (the number of 0s in the best window = number of swaps needed).

def minSwaps(data: list[int]) -> int:
    k = sum(data)  # number of 1s = window size
    if k == 0 or k == len(data):
        return 0
    
    # Count 1s in initial window
    ones = sum(data[:k])
    max_ones = ones
    
    for i in range(k, len(data)):
        ones += data[i] - data[i - k]  # slide window
        max_ones = max(max_ones, ones)
    
    return k - max_ones

Algorithm Flow

Dry Run

data = [1,0,1,0,1], k=3

Initial window [1,0,1]: ones=2, max_ones=2

i	data[i]	data[i-3]	ones	max_ones
3	0	1	2+0-1=1	2
4	1	0	1+1-0=2	2

Answer: k - max_ones = 3 - 2 = 1 ✓

Edge Cases

• All zeros → return 0 (k=0)
• All ones → return 0 (k=n, already grouped)
• Single one → return 0 (k=1, always grouped)

Complexity

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

Key Terms

Term	Definition
Sliding window	Fixed-size window moved across the array, updating a running aggregate in O(1) per step.
Fixed window size	Here the window size equals k, the total count of 1s, since that's the minimum span needed to hold them all.
Swap	Exchanging a 0 inside the window with a 1 outside it — one swap per misplaced 0.
Circular array variant	A version of this problem where the array wraps around, requiring the window to also span the end-to-start boundary.

FAQ

Q: Why is the window size fixed at k (total number of 1s)? A: Any valid final grouping of all 1s occupies exactly k contiguous cells, so the best window is one of size k — we just need to find the one with the most 1s already in it.

Q: Why does k - max_ones give the swap count? A: The window with max_ones needs k - max_ones of its 0s replaced by 1s from outside — each replacement is exactly one swap.

Q: What if there are no 1s or the array is all 1s? A: Both are already "grouped" (trivially), so the answer is 0 — handled by the early return when k == 0 or k == len(data).

Q: How would this change if the array were circular? A: You'd also need to check windows that wrap around the end and beginning, typically by concatenating data with itself and capping the window search within one full length.

Q: Can this be solved without a sliding window? A: Yes, with prefix sums to compute ones-in-range in O(1) per window, but sliding window is simpler and equally O(n).

Quick Revision

• Count total 1s → this is the required window size k.
• Slide a window of size k; track the max number of 1s inside any such window.
• Answer = k - max_ones (number of 0s to swap out in the best window).
• Early exit when k == 0 or k == len(data) → answer is 0.
• Window update: ones += data[i] - data[i-k].
• Time O(n), Space O(1).
• Contrast with variable-size sliding window problems (e.g., longest substring) — here the size is fixed and known upfront.

Related Problems

• 3 - Longest Substring Without Repeating Characters — variable-size sliding window pattern for comparison.
• 1695 - Maximum Erasure Value — another fixed-set sliding window optimization problem.