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:

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

Examples

Example 1:

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:

2

So the answer is:

2

Example 2:

seats = [1, 0, 0, 0]

The best choice is the last seat.

The closest person is at index 0.

The distance is:

3

So the answer is:

3

Example 3:

seats = [0, 1]

The only empty seat is index 0.

The closest person is at index 1.

So the answer is:

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.

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:

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:

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:

(right - left) // 2

For an edge gap:

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:

   len(seats) - last - 1
   

5. Return the maximum answer.

Walkthrough

Use:

seats = [1, 0, 0, 0, 1, 0, 1]

Occupied seats are at:

0, 4, 6

Between 0 and 4, the best distance is:

(4 - 0) // 2 = 2

Between 4 and 6, the best distance is:

(6 - 4) // 2 = 1

There is no leading empty prefix.

There is no trailing empty suffix.

So the answer is:

2

Now use:

seats = [1, 0, 0, 0]

The only occupied seat is at index 0.

The trailing empty suffix length is:

4 - 0 - 1 = 3

So the answer is:

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:

min(i - left, right - i)

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

(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

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:

last = -1

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

When we see the first occupied seat:

if last == -1:
    answer = i

the leading empty prefix has length i.

For later occupied seats:

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:

last = i

Finally, handle the trailing empty suffix:

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

Then return the best value.

Testing

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