700. Gathering Every One Together
An array holds only 0 and 1. One swap exchanges any two positions. Print the fewest swaps needed to bring every 1 into one contiguous block.
1 0 1 0 1 -> 1
1 0 1 1 0 1 -> 1
1 1 1 -> 0
0 0 0 -> 0
## Where the block ends up
Let m be the total number of ones. Whatever the final block is, it occupies exactly m
consecutive positions. So there are only n - m + 1 possible destinations, one per window of
length m.
Fixing the window LENGTH from a property of the input, rather than from a parameter, is the step this problem is really testing.
## The cost of a chosen destination
A window of length m already holding t ones is missing m - t of them, and each missing
one is fixed by a single swap: take a one from outside and a zero from inside.
Those two sets have the same size, m - t, so the swaps pair up exactly and no swap is wasted.
The cost is m - t, and the answer is
m - (the most ones in any window of length m)
## The sweep
cur = ones in a[0 .. m-1]
best = cur
for i in m .. n-1:
cur += a[i] - a[i - m]
best = max(best, cur)
answer = m - best
## The case that breaks a careless version
m = 0, an array of all zeros. There is nothing to gather, the answer is 0, and a window of
length 0 is not something the loop can build. Handle it before the sweep.
m = n is the other end: one window, already full, answer 0.
## Why a greedy "move each one to the nearest gap" fails
It has no way to decide where the block should be, and different choices give different totals.
Trying every destination is only O(n) here, so there is no reason to guess.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - each value is `0` or `1`
Input
The first line contains an integer n.
The second line contains n integers, each 0 or 1.
Output
Print one integer, the fewest swaps.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.