630. How Far to the Nearest Marked Spot
A row of n positions is given, each marked (1) or unmarked (0). At least one position is
marked.
For every position, print the distance to the nearest marked position, where the distance
between positions i and j is |i - j|. A marked position is at distance 0 from itself.
0 0 1 0 0 -> 2 1 0 1 2
0 1 0 1 0 -> 1 0 1 0 1
1 0 0 0 -> 0 1 2 3
## Why one pass cannot do it
Sweeping left to right and remembering the last mark gives the distance to the nearest mark ON
THE LEFT. It has no way to know about a mark that is still ahead, so on 0 0 1 it reports
nothing for the first two positions.
The nearest mark is either to the left or to the right, and those are two different questions. So the answer is two sweeps, one in each direction, combined by taking the smaller.
## The two sweeps
left to right: remember the most recent mark; d[i] = i - last (skip while none seen)
right to left: remember the most recent mark; d[i] = min(d[i], last - i)
Each sweep is one pointer walking the row while a second index trails behind it at the last mark. Neither index ever goes backwards within its own sweep.
## Why taking the minimum of the two is correct
Every mark is either at or before i, or after i. The first sweep finds the closest of the
former and the second finds the closest of the latter, so between them every mark has been
considered. The nearest overall is the smaller of the two.
## The sentinel, and why it must survive addition
Before the first mark is seen in a sweep, there is no distance to record. Use a value large enough that the second sweep always beats it, and make sure it is not so large that anything added to it overflows.
Here n is at most 200000, so any distance is below that; a sentinel of 10^9 is safe and
comfortably above every real answer.
Since at least one position is marked, no entry keeps the sentinel at the end.
## Cost
Time O(n) in two passes. Space O(n) for the answer.
Constraints - `1 ≤ n ≤ 200000` - each value is `0` or `1` - at least one value is `1`
Input
The first line contains an integer n.
The second line contains n integers, each 0 or 1, with at least one 1.
Output
Print n integers on one line, separated by single spaces: the distance from each
position to the nearest marked position.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.