LeetCode 849 - Maximize Distance to Closest Person

In this problem, we are given a binary array called seats. Each position in the array represents a seat in a row: - 1 means the seat is occupied. - 0 means the seat is empty.

leetcodemediumarray

LeetCode Problem 849

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

In this problem, we are given a binary array called seats. Each position in the array represents a seat in a row:

  • 1 means the seat is occupied.
  • 0 means the seat is empty.

We need to determine where Alex should sit so that the distance to the nearest occupied seat is as large as possible. The final answer is that maximum possible minimum distance.

The key detail is that we are not maximizing the distance to every person, we are maximizing the distance to the closest person. For any empty seat, we compute the distance to the nearest occupied seat. Among all empty seats, we choose the seat with the largest such distance.

For example:

[1,0,0,0,1]

If Alex sits in the middle empty seat:

[1,0,X,0,1]

the nearest occupied seat is two positions away on either side, so the minimum distance is 2.

The constraints are important:

  • 2 <= seats.length <= 2 * 10^4
  • The array contains only 0 and 1
  • There is at least one empty seat
  • There is at least one occupied seat

Since the array length can reach twenty thousand elements, we should aim for a linear time solution, O(n). Quadratic approaches may still pass at this size in some languages, but they are inefficient and unnecessary.

Several edge cases are especially important:

  • Empty seats at the beginning of the array

  • Example: [0,0,0,1]

  • Empty seats at the end of the array

  • Example: [1,0,0,0]

  • Empty seats between two occupied seats

  • Example: [1,0,0,0,1]

  • Very small arrays

  • Example: [0,1]

A naive implementation can easily mishandle leading or trailing zeros because those cases are not symmetric with middle gaps.

Approaches

Brute Force Approach

The brute force strategy is straightforward. For every empty seat:

  1. Scan left until finding an occupied seat.
  2. Scan right until finding an occupied seat.
  3. Compute the distance to the closest occupied seat.
  4. Track the maximum among all empty seats.

This approach is correct because it explicitly evaluates every possible sitting position and computes the exact nearest-person distance for each one.

However, it is inefficient. Suppose there are n seats. For every empty seat, we may scan almost the entire array in both directions. In the worst case, this leads to O(n^2) time complexity.

With n = 20,000, quadratic behavior is unnecessarily slow compared to a linear solution.

Optimal Approach

The important observation is that the answer depends on stretches of consecutive empty seats.

There are three distinct situations:

  1. Empty seats at the beginning
  2. Empty seats at the end
  3. Empty seats between two occupied seats

For middle segments, the best seat is always the middle of the gap. If a gap length is k, the best achievable distance is:

(k + 1) // 2

For leading or trailing gaps, Alex can sit at the farthest end, so the distance equals the entire gap length.

Instead of evaluating every empty seat independently, we can process contiguous blocks of zeros and compute their contribution directly. This reduces the runtime to O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Check every empty seat by scanning left and right
Optimal O(n) O(1) Process consecutive zero segments directly

Algorithm Walkthrough

Optimal Linear Scan Algorithm

  1. Initialize variables to track the best answer and the index of the previous occupied seat.

We use:

  • max_distance to store the best result found so far
  • previous_person to remember the index of the last occupied seat

Initially, previous_person = -1 because we have not seen any occupied seat yet. 2. Traverse the array from left to right.

For every index i:

  • If seats[i] == 0, continue scanning.
  • If seats[i] == 1, we found an occupied seat and can evaluate the gap before it.
  1. Handle the first occupied seat separately.

If previous_person == -1, then this is the first occupied seat in the array.

The distance contributed by leading zeros is simply:

i

because Alex could sit at index 0. 4. Handle middle gaps.

If we already saw a previous occupied seat, then the zeros between:

previous_person and i

form a middle gap.

The gap size is:

i - previous_person

The best possible distance inside this gap is:

(i - previous_person) // 2

because the optimal seat is near the center. 5. Update previous_person.

After processing the current occupied seat, set:

previous_person = i
  1. Handle trailing zeros after the loop finishes.

If the last occupied seat is at index previous_person, then trailing zeros contribute:

len(seats) - 1 - previous_person

because Alex could sit at the final seat. 7. Return the maximum distance found.

Why it works

The algorithm works because every empty seat belongs to exactly one of three categories:

  • Leading zeros
  • Trailing zeros
  • Zeros between occupied seats

For middle gaps, the optimal position is always the midpoint because moving toward either occupied seat decreases the minimum distance. For edge gaps, the farthest endpoint is optimal because there is only one nearby occupied seat.

Since the algorithm evaluates every zero segment exactly once and computes the mathematically optimal distance for that segment, the final maximum is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        max_distance = 0
        previous_person = -1

        for i, seat in enumerate(seats):
            if seat == 1:
                if previous_person == -1:
                    # Leading zeros
                    max_distance = i
                else:
                    # Middle gap
                    gap_distance = (i - previous_person) // 2
                    max_distance = max(max_distance, gap_distance)

                previous_person = i

        # Trailing zeros
        trailing_distance = len(seats) - 1 - previous_person
        max_distance = max(max_distance, trailing_distance)

        return max_distance

The implementation follows the algorithm directly.

We begin by initializing max_distance and previous_person. The variable previous_person stores the index of the most recent occupied seat encountered during traversal.

As we iterate through the array, we only perform work when encountering a 1. This is because occupied seats define the boundaries of zero segments.

If this is the first occupied seat, then all preceding positions are leading zeros. The distance contribution equals the index itself.

Otherwise, we compute the midpoint distance for the gap between consecutive occupied seats using integer division.

After processing all occupied seats, we handle trailing zeros separately because they are not processed inside the loop.

The solution uses constant extra memory and processes the array in a single pass.

Go Solution

package main

func maxDistToClosest(seats []int) int {
	maxDistance := 0
	previousPerson := -1

	for i, seat := range seats {
		if seat == 1 {
			if previousPerson == -1 {
				// Leading zeros
				maxDistance = i
			} else {
				// Middle gap
				gapDistance := (i - previousPerson) / 2
				if gapDistance > maxDistance {
					maxDistance = gapDistance
				}
			}

			previousPerson = i
		}
	}

	// Trailing zeros
	trailingDistance := len(seats) - 1 - previousPerson
	if trailingDistance > maxDistance {
		maxDistance = trailingDistance
	}

	return maxDistance
}

The Go implementation closely mirrors the Python version.

Go uses explicit integer division with /, which automatically truncates toward zero for integers, matching the desired midpoint calculation.

Unlike Python, Go does not provide a built-in max function for integers, so comparisons are performed manually with if statements.

Slices are used naturally for the input array, and no additional allocations are required.

Worked Examples

Example 1

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

Initial state:

Variable Value
max_distance 0
previous_person -1

Iteration Trace

Index Seat Action max_distance previous_person
0 1 First occupied seat, leading distance = 0 0 0
1 0 Skip 0 0
2 0 Skip 0 0
3 0 Skip 0 0
4 1 Middle gap = (4 - 0) // 2 = 2 2 4
5 0 Skip 2 4
6 1 Middle gap = (6 - 4) // 2 = 1 2 6

Trailing zeros:

6 - 6 = 0

Final answer:

2

Example 2

seats = [1,0,0,0]

Iteration Trace

Index Seat Action max_distance previous_person
0 1 First occupied seat 0 0
1 0 Skip 0 0
2 0 Skip 0 0
3 0 Skip 0 0

Trailing zeros:

3 - 0 = 3

Final answer:

3

Example 3

seats = [0,1]

Iteration Trace

Index Seat Action max_distance previous_person
0 0 Skip 0 -1
1 1 Leading distance = 1 1 1

Trailing zeros:

1 - 1 = 0

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n) The array is traversed exactly once
Space O(1) Only a few variables are used

The algorithm performs a single linear scan across the input array. Every seat is processed once, and all operations inside the loop are constant time operations.

No auxiliary data structures proportional to input size are allocated, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        max_distance = 0
        previous_person = -1

        for i, seat in enumerate(seats):
            if seat == 1:
                if previous_person == -1:
                    max_distance = i
                else:
                    gap_distance = (i - previous_person) // 2
                    max_distance = max(max_distance, gap_distance)

                previous_person = i

        trailing_distance = len(seats) - 1 - previous_person
        max_distance = max(max_distance, trailing_distance)

        return max_distance

solution = Solution()

assert solution.maxDistToClosest([1,0,0,0,1,0,1]) == 2  # Standard middle-gap example
assert solution.maxDistToClosest([1,0,0,0]) == 3  # Trailing zeros
assert solution.maxDistToClosest([0,1]) == 1  # Leading zero
assert solution.maxDistToClosest([1,0]) == 1  # Single trailing zero
assert solution.maxDistToClosest([0,0,0,1]) == 3  # Large leading gap
assert solution.maxDistToClosest([1,0,0,1]) == 1  # Even-sized middle gap
assert solution.maxDistToClosest([1,0,0,0,0,1]) == 2  # Larger middle gap
assert solution.maxDistToClosest([1,0,1,0,0,0]) == 3  # Trailing gap larger than middle
assert solution.maxDistToClosest([0,1,0,0,0,1,0]) == 2  # Leading and trailing zeros
assert solution.maxDistToClosest([1,0,0,0,0,0,1]) == 3  # Odd-sized middle gap
Test Why
[1,0,0,0,1,0,1] Standard example with middle gap
[1,0,0,0] Tests trailing zeros
[0,1] Tests leading zero handling
[1,0] Smallest trailing-gap case
[0,0,0,1] Large leading gap
[1,0,0,1] Even-sized middle segment
[1,0,0,0,0,1] Larger middle segment
[1,0,1,0,0,0] Trailing gap dominates
[0,1,0,0,0,1,0] Combination of edge and middle gaps
[1,0,0,0,0,0,1] Odd-sized middle gap

Edge Cases

Leading Empty Seats

A common source of bugs occurs when the array begins with zeros, such as:

[0,0,0,1]

In this case, the best seat is at the far left edge. A naive midpoint formula does not work because there is no occupied seat on the left side.

The implementation handles this by detecting the first occupied seat separately using:

if previous_person == -1:

The distance is simply the index of the first occupied seat.

Trailing Empty Seats

Another important edge case occurs when the array ends with zeros:

[1,0,0,0]

The best seat is at the far right edge, with distance 3.

This case is easy to miss because the loop only processes gaps when encountering occupied seats. Since no occupied seat appears after the trailing zeros, they must be handled after the loop finishes.

The implementation computes:

len(seats) - 1 - previous_person

to correctly measure the trailing gap.

Middle Gaps With Even and Odd Lengths

Middle gaps require careful integer division behavior.

For example:

[1,0,0,0,1]

The optimal distance is:

(4 - 0) // 2 = 2

For an even-sized gap:

[1,0,0,1]

the best distance becomes:

(3 - 0) // 2 = 1

Using integer division correctly ensures that the nearest occupied seat distance is computed accurately for both odd and even gap lengths.