#849

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Maximize Distance to Closest Person

Determine the seat placement that maximizes distance to the nearest person using a linear array scan strategy efficiently.

array

Problem Statement

You are given a row of seats represented as an array where seats[i] = 1 indicates the seat is occupied and seats[i] = 0 indicates it is empty. Alex wants to choose a seat that maximizes his distance from the nearest occupied seat.

Your task is to return the maximum possible distance Alex can achieve by selecting the optimal empty seat. Consider all empty positions, including edge seats and consecutive empty gaps, when determining the farthest possible distance from other people.

Examples

Example 1

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

Output: 2

If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2. If Alex sits in any other open seat, the closest person has distance 1. Thus, the maximum distance to the closest person is 2.

Example 2

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

Output: 3

If Alex sits in the last seat (i.e. seats[3]), the closest person is 3 seats away. This is the maximum distance possible, so the answer is 3.

Example 3

Input: seats = [0,1]

Output: 1

Example details omitted.

Constraints

2 <= seats.length <= 2 * 104
seats[i] is 0 or 1.
At least one seat is empty.
At least one seat is occupied.

Solution Approach

Identify consecutive empty seats

Scan the array from left to right to track lengths of consecutive zeros. The maximum distance within the array is often half the size of the largest consecutive empty segment.

Handle leading and trailing zeros

Special cases occur at the start or end of the row. If the first or last seat is empty, Alex can sit at the edge, yielding a distance equal to the number of consecutive empty seats from the closest person.

Compute the maximum distance efficiently

Compare distances from leading zeros, trailing zeros, and internal gaps. Return the largest value as the maximum distance, ensuring all edge cases are included in a single linear pass.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is $O(N)$ because the array is traversed once to track empty gaps. Space complexity is $O(1)$ since only counters for distances are maintained without additional storage proportional to input size.

What Interviewers Usually Probe

Asks about handling edge seats separately from middle segments.
Questions why a simple mid-gap division works for consecutive empty seats.
Explores if the solution can be done in one pass without extra arrays.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for empty seats at the beginning or end of the array.
Using integer division incorrectly when computing half-gaps inside the array.
Scanning multiple times instead of maintaining running counters, increasing time complexity unnecessarily.

Follow-up variants

What if multiple people can be seated sequentially to maximize distance?
Consider a circular row where the first and last seats are adjacent.
Modify the array to include reserved seats that cannot be chosen and recalculate maximum distance.

FAQ

How do you handle leading and trailing empty seats in Maximize Distance to Closest Person?

Treat leading or trailing zeros as special cases; the distance is the number of consecutive empty seats up to the nearest occupied seat.

Can this problem be solved in one pass with constant space?

Yes, by tracking current consecutive empty seats and updating the maximum distance during a single linear scan.

Why is the maximum distance often half the largest internal gap?

Because the optimal seat in the middle of a consecutive empty segment places Alex at equal distance from both neighboring occupied seats.

What if all seats are empty except one?

The maximum distance is the length of the longest gap from the single occupied seat, which will be at one of the edges.

Does the array-driven solution pattern apply to other seating optimization problems?

Yes, the same approach works for any linear seating arrangement where maximizing minimum distance is required.

terminal

Solution

Solution 1: Single Traversal

We define two variables $\textit{first}$ and $\textit{last}$ to represent the positions of the first and last person, respectively. We use the variable $d$ to represent the maximum distance between two people.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        first = last = None
        d = 0
        for i, c in enumerate(seats):
            if c:
                if last is not None:
                    d = max(d, i - last)
                if first is None:
                    first = i
                last = i
        return max(first, len(seats) - last - 1, d // 2)

Continue Practicing

#848 shifting letters #850 rectangle area ii #851 loud and rich