Maximize Distance to Closest Person (LeetCode 849)

Problem Statement

You are given an array seats where seats[i] = 1 means seat i is occupied, and seats[i] = 0 means it is empty. There is at least one empty seat and at least one occupied seat.

Alex wants to sit so that the distance between him and the closest occupied seat is maximized. Return the maximum distance to the closest person.

Constraints

• 1 <= seats.length <= 2^12
• seats[i] is either 0 or 1.
• At least one 0 and at least one 1 in seats.

Examples

Example 1

Input: seats = [1,0,0,0,1,0,1]

Output: 4

Explanation: The maximum distance to the closest person is 4 seats away (the seat marked with the red circle).

Example 2

Input: seats = [1,0,0,0]

Output: 3

Explanation: There are two possible scenarios to sit (seats 2 or 3) with a maximum distance of 3 seats away from the closest person.

Example 3

Input: seats = [0,1,0,0,1,1,1,0]

Output: 4

Hints

1. Consider the distance between two consecutive occupied seats.
2. Think about the distance from the first and last occupied seat to the nearest empty seat.