# LeetCode 849: Maximize Distance to Closest Person

## Problem Restatement

We are given an array `seats`.

Each value means:

| Value | Meaning |
|---|---|
| `1` | Someone is sitting in this seat |
| `0` | This seat is empty |

Alex wants to choose one empty seat so that the distance to the closest person is as large as possible.

Return that maximum distance.

There is at least one empty seat and at least one occupied seat.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary array `seats` |
| Output | Maximum possible distance to the closest person |
| Empty seat | `0` |
| Occupied seat | `1` |
| Distance | Absolute difference between seat indices |

Function shape:

```python
class Solution:
    def maxDistToClosest(self, seats: list[int]) -> int:
        ...
```

## Examples

Example 1:

```python
seats = [1, 0, 0, 0, 1, 0, 1]
```

The best choice is index `2`.

Its closest occupied seat is index `0` or index `4`.

The distance is:

```python
2
```

So the answer is:

```python
2
```

Example 2:

```python
seats = [1, 0, 0, 0]
```

The best choice is the last seat.

The closest person is at index `0`.

The distance is:

```python
3
```

So the answer is:

```python
3
```

Example 3:

```python
seats = [0, 1]
```

The only empty seat is index `0`.

The closest person is at index `1`.

So the answer is:

```python
1
```

## First Thought: Try Every Empty Seat

A direct solution is to test every empty seat.

For each empty seat, scan the whole array to find the nearest occupied seat.

Then keep the maximum of those nearest distances.

```python
class Solution:
    def maxDistToClosest(self, seats: list[int]) -> int:
        n = len(seats)
        answer = 0

        for i in range(n):
            if seats[i] == 0:
                closest = n

                for j in range(n):
                    if seats[j] == 1:
                        closest = min(closest, abs(i - j))

                answer = max(answer, closest)

        return answer
```

This is correct, but it scans the full array for every empty seat.

## Problem With Brute Force

If there are `n` seats, the brute force solution can take:

```python
O(n^2)
```

The constraints allow up to `2 * 10^4` seats, so a quadratic solution is unnecessary.

We can do better by looking at gaps between occupied seats.

## Key Insight

Only three kinds of empty regions matter:

| Region type | Best distance |
|---|---:|
| Empty seats before the first occupied seat | Length of that prefix |
| Empty seats after the last occupied seat | Length of that suffix |
| Empty seats between two occupied seats | Half the gap, rounded down |

For a middle gap:

```python
1 0 0 0 1
```

There are two occupied seats around the empty block.

The best position is in the middle.

If the two occupied seats are at indices `left` and `right`, then the best distance is:

```python
(right - left) // 2
```

For an edge gap:

```python
0 0 0 1
```

Alex can sit at the far end, so the distance is the full number of empty seats before the first person.

## Algorithm

Scan the array from left to right and record the last occupied seat.

1. Initialize `last = -1`.
2. Initialize `answer = 0`.
3. For each index `i`:
   1. If `seats[i] == 1`:
      1. If this is the first occupied seat, update `answer` with `i`.
      2. Otherwise, update `answer` with `(i - last) // 2`.
      3. Set `last = i`.
4. After the scan, check the trailing empty seats:
   ```python id="gs79sb"
   len(seats) - last - 1
   ```
5. Return the maximum answer.

## Walkthrough

Use:

```python
seats = [1, 0, 0, 0, 1, 0, 1]
```

Occupied seats are at:

```python
0, 4, 6
```

Between `0` and `4`, the best distance is:

```python
(4 - 0) // 2 = 2
```

Between `4` and `6`, the best distance is:

```python
(6 - 4) // 2 = 1
```

There is no leading empty prefix.

There is no trailing empty suffix.

So the answer is:

```python
2
```

Now use:

```python
seats = [1, 0, 0, 0]
```

The only occupied seat is at index `0`.

The trailing empty suffix length is:

```python
4 - 0 - 1 = 3
```

So the answer is:

```python
3
```

## Correctness

Every possible empty seat belongs to exactly one of three regions: before the first occupied seat, after the last occupied seat, or between two consecutive occupied seats.

For an empty prefix before the first occupied seat, the farthest valid seat is index `0`, and its closest person is the first occupied seat. The best distance is the prefix length.

For an empty suffix after the last occupied seat, the farthest valid seat is the last index, and its closest person is the last occupied seat. The best distance is the suffix length.

For an empty block between occupied seats at `left` and `right`, any chosen seat has closest distance:

```python
min(i - left, right - i)
```

This value is maximized by choosing a seat nearest the middle of the interval, giving:

```python
(right - left) // 2
```

The algorithm computes the best value for every such region and returns the maximum. Therefore, it returns the largest possible distance to the closest person.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One scan through the seats |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def maxDistToClosest(self, seats: list[int]) -> int:
        n = len(seats)
        answer = 0
        last = -1

        for i, seat in enumerate(seats):
            if seat == 1:
                if last == -1:
                    answer = i
                else:
                    answer = max(answer, (i - last) // 2)

                last = i

        answer = max(answer, n - last - 1)
        return answer
```

## Code Explanation

We use `last` to remember the most recent occupied seat:

```python
last = -1
```

The value `-1` means we have not seen any occupied seat yet.

When we see the first occupied seat:

```python
if last == -1:
    answer = i
```

the leading empty prefix has length `i`.

For later occupied seats:

```python
answer = max(answer, (i - last) // 2)
```

we compute the best distance in the middle gap between `last` and `i`.

After processing each occupied seat, update:

```python
last = i
```

Finally, handle the trailing empty suffix:

```python
answer = max(answer, n - last - 1)
```

Then return the best value.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxDistToClosest([1, 0, 0, 0, 1, 0, 1]) == 2
    assert s.maxDistToClosest([1, 0, 0, 0]) == 3
    assert s.maxDistToClosest([0, 1]) == 1
    assert s.maxDistToClosest([0, 0, 1]) == 2
    assert s.maxDistToClosest([1, 0, 1]) == 1
    assert s.maxDistToClosest([1, 0, 0, 1]) == 1
    assert s.maxDistToClosest([1, 0, 0, 0, 0, 1]) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Confirms middle gap handling |
| Trailing empty seats | Confirms suffix case |
| Leading empty seats | Confirms prefix case |
| Longer leading prefix | Confirms distance to first person |
| One empty middle seat | Confirms smallest middle gap |
| Even middle gap | Confirms floor division |
| Long middle gap | Confirms best seat is near the center |