Maximize Distance to Closest Person: Gap Scanning

You are given an array seats where seats[i] = 1 means the seat is occupied and seats[i] = 0 means it is empty. At least one seat is occupied and at least one is empty. You want to sit in an empty seat so that you maximize the distance to the nearest occupied seat. Return that maximum distance.

This is LeetCode 849: Maximize Distance to Closest Person, a medium problem that tests your ability to reason about gaps in arrays. The trick is recognizing three distinct gap types, and handling each one correctly in a single scan.

Why this problem matters

Maximize Distance to Closest Person is a clean example of gap analysis on a linear array. You need to find contiguous runs of empty seats, compute the best possible position within each run, and take the overall maximum. This same pattern appears in problems about placing elements with spacing constraints, scheduling with buffers, and interval-based optimization.

The problem also teaches you to handle boundary conditions carefully. Gaps at the beginning and end of the array behave differently from gaps in the middle, and getting that distinction right is the core challenge.

The brute force approach

The most natural approach is to check every empty seat, compute its distance to the nearest occupied seat, and track the maximum.

def max_dist_to_closest_brute(seats):
    n = len(seats)
    best = 0
    for i in range(n):
        if seats[i] == 0:
            dist = n
            for j in range(n):
                if seats[j] == 1:
                    dist = min(dist, abs(i - j))
            best = max(best, dist)
    return best

This works, but it runs in O(n^2) time. For each empty seat you scan the entire array to find the closest person. With inputs up to 2 * 10^4 seats, this is unnecessarily slow. The problem is that you are recomputing distances from scratch for every candidate seat instead of leveraging the structure of the gaps.

The key insight: gaps between occupied seats

Every empty seat belongs to exactly one gap: a contiguous run of zeros bounded by either an occupied seat or the edge of the array. You do not need to check every seat individually. Instead, you can examine each gap and compute the best distance achievable within that gap.

There are three types of gaps:

1. Leading gap: empty seats before the first occupied seat. If you sit at the very start (index 0), your distance equals the index of the first person.
2. Middle gap: empty seats between two occupied seats. The best seat is in the middle of the gap, giving distance floor(gap_length / 2) where gap_length is the distance between the two occupied seats.
3. Trailing gap: empty seats after the last occupied seat. If you sit at the very end (index n-1), your distance equals n - 1 - last_person_index.

Walking through it step by step

Let's trace through seats = [1, 0, 0, 0, 1, 0, 1]. The answer is 2 (sit at index 2).

The leading gap is empty because the first person sits at index 0. The middle gap between indices 0 and 4 has 3 empty seats, and the middle position (index 2) gives distance 2. The middle gap between indices 4 and 6 has 1 empty seat giving distance 1. The trailing gap is empty because the last person sits at index 6. The best distance is 2.

The gap scanning solution

Here is the complete solution in Python:

def max_dist_to_closest(seats):
    n = len(seats)
    prev = -1
    best = 0

    for i in range(n):
        if seats[i] == 1:
            if prev == -1:
                best = i
            else:
                best = max(best, (i - prev) // 2)
            prev = i

    best = max(best, n - 1 - prev)
    return best

Here is what each piece does:

1. prev = -1 tracks the index of the last occupied seat we have seen. Starting at -1 signals that we have not yet encountered any person.
2. Leading gap: the first time we hit an occupied seat (prev == -1), the leading gap distance is simply i, the index of that first person. Sitting at index 0 gives you that much distance.
3. Middle gaps: for every subsequent occupied seat, the gap between prev and i has i - prev - 1 empty seats. The best position is in the middle, giving distance (i - prev) // 2. We use integer division because when the gap has an even number of empty seats, you cannot sit exactly in the center.
4. Trailing gap: after the loop, prev holds the index of the last occupied seat. The trailing gap distance is n - 1 - prev, representing how far the last seat (index n-1) is from the last person.
5. Return best, the maximum across all three gap types.

Complexity analysis

You need to inspect every seat at least once, so O(n) is optimal. The algorithm uses only two extra variables regardless of input size.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Gap analysis

The pattern of scanning for contiguous segments of a specific value and computing properties of each segment:

prev = -1
for i in range(n):
    if condition(i):
        gap = i - prev - 1
        process_gap(prev, i, gap)
        prev = i

In Maximize Distance, the condition is seats[i] == 1 and you compute the best seating position within each gap. In Can Place Flowers, you scan for gaps between planted flowers to determine how many new flowers fit. The skeleton is the same. Only the gap processing logic changes.

2. Edge handling for boundaries

The idea that boundary gaps (at the start or end of the array) require different logic than interior gaps. In an interior gap, you sit in the middle because both sides have an occupied seat. At a boundary, you sit at the far edge because there is no person beyond the boundary.

This asymmetry between edge and interior segments shows up in many array problems. Trapping Rain Water needs special treatment for the first and last bars. Candy treats the first and last children differently in each pass. Recognizing when boundary conditions need separate handling is a transferable skill.

Edge cases

Before submitting, make sure your solution handles these:

• One person at the start [1, 0, 0, 0]: the trailing gap is length 3, so the answer is 3. Sit at the far end.
• One person at the end [0, 0, 0, 1]: the leading gap is length 3, so the answer is 3. Sit at index 0.
• One person in the middle [0, 0, 1, 0, 0]: leading gap is 2, trailing gap is 2. The answer is 2.
• All adjacent people with one gap [1, 1, 0, 1, 1]: the only gap has 1 empty seat, so the answer is 1.
• Two seats [1, 0] or [0, 1]: the answer is always 1.
• Large gap in the middle [1, 0, 0, 0, 0, 0, 1]: 5 empty seats between two people. Sitting in the middle gives distance 3.

The gap scanning solution handles all of these without special-case logic.

From understanding to recall

You have read the gap scanning solution and it makes sense. One loop, three gap types, one max. But can you write it from scratch in an interview without looking at it?

The details matter: initializing prev to -1, handling the leading gap as a special case when prev == -1, using integer division for middle gaps, and remembering to check the trailing gap after the loop ends. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the gap scanning loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "find the optimal position within gaps" and the code flows out without hesitation.

The gap analysis pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Can Place Flowers - Another gap-based array problem with adjacency constraints
• Gas Station - Single-pass scan with tracking of the best candidate
• Find Peak Element - Scanning for optimal positions in arrays

CodeBricks breaks the maximize distance to closest person LeetCode problem into its gap analysis and boundary handling building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a gap scanning question shows up in your interview, you do not think about it. You just write it.