522. Maximize Distance to Closest Person
A row of seats is given as the array seats, where seats[i] = 1 means someone is sitting in seat i and seats[i] = 0 means the seat is free. There is at least one person and at least one free seat.
Alex wants to pick a free seat whose distance to the nearest occupied seat is as large as possible (distance between seats i and j is |i − j|).
Return that largest possible distance — the value itself, not the seat index.
Example 1:
Input: seats = [1, 0, 0, 0, 1, 0, 1]
Output: 2
Explanation: Sitting at index 2 puts Alex two seats away from the people at indices 0 and 4. Every other free seat has someone within distance 1.
Example 2:
Input: seats = [1, 0, 0, 0]
Output: 3
Explanation: The row ends in open seats, so Alex takes the last one, three seats from the only person.
Example 3:
Input: seats = [0, 1]
Output: 1
Explanation: The only free seat is index 0, at distance 1 from the person in seat 1.
Constraints:
- 2 ≤ seats.length ≤ 2 * 10⁴
- seats[i] is 0 or 1
- At least one seat is occupied and at least one seat is empty.
Hints:
For any candidate seat, its distance to the closest person is what matters. Doing this literally — for each empty seat, find the nearest 1 — already works, just slowly.
Think in gaps. A stretch of k empty seats between two people lets Alex sit in its middle, at distance ⌈k / 2⌉ = (j − i) / 2 for people at i and j. A stretch at either end of the row is better: he sits at the very edge and gets the whole gap length. One pass over the positions of the 1s covers all three cases.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: seats = [1, 0, 0, 0, 1, 0, 1]
Expected output: 2