LeetCode 849: Maximize Distance to Closest Person

Problem Restatement

We are given an array seats.

Each value means:

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

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:

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

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: