653. The Seat Furthest From Anyone
A row of seats is given, each 1 for taken and 0 for free. At least one seat is taken and at
least one is free.
Choose a free seat so that the distance to the NEAREST taken seat is as large as possible, and print that distance.
1 0 0 0 1 0 1 -> 2 sitting at position 2
1 0 0 0 -> 3 sitting at the far end
0 1 -> 1 sitting at position 0
## Three kinds of gap, and only three
Walk the taken seats in order. Every free seat lies in exactly one of:
· a gap BEFORE the first taken seat. The best is the very first seat, at distance equal to
the index of that first taken seat.
· a gap BETWEEN two taken seats at p and q. The best is the middle, at distance
(q - p) / 2, rounded DOWN.
· a gap AFTER the last taken seat. The best is the very last seat, at distance
n - 1 - last.
Take the largest over all three kinds. One pass, remembering only the previous taken seat.
## Why the middle gap rounds down
Between p and q there are q - p - 1 free seats. Sitting exactly halfway gives distance
(q - p) / 2 when the gap is even, and the two central seats tie at (q - p - 1) / 2 when it
is odd. Integer division by 2 gives both, which is why the formula needs no case split.
1 0 1 answers 1 and 1 0 0 1 answers 1 as well: with two free seats in the middle, neither
is further than 1 from someone.
That second input is the one to trace, because it looks like it should answer 2.
## Why the two end gaps are different
An end gap is bounded on ONE side only, so the best seat is the extreme end and the distance is the whole gap, not half of it. Treating the ends with the middle formula halves them and is the usual error.
1 0 0 0 answers 3, not 1.
## Why this is a two-pointer sweep
One index walks the row and a second trails at the most recent taken seat. Neither moves backwards, and the answer is assembled from the distances between consecutive positions of the trailing index, which is the same discipline as problem 630.
## Cost
Time O(n) in one pass. Space O(1).
Constraints - `2 ≤ n ≤ 200000` - each value is `0` or `1` - at least one seat is taken and at least one is free
Input
The first line contains an integer n.
The second line contains n integers, each 0 or 1, with at least one of each.
Output
Print one integer, the largest possible distance to the nearest taken seat.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.