Maximize Distance to Closest Person

Maximize Distance to Closest Person

What is this problem about?

You are given an array representing a row of seats in a theater, where 1 represents an occupied seat and 0 represents an empty seat. You want to sit in an empty seat such that your distance to the closest person already sitting there is maximized. You must return that maximum distance.

Why is this asked in interviews?

This is a classic linear array traversal problem. Interviewers use it to see if a candidate can handle three distinct edge cases elegantly: sitting at the far left edge, sitting at the far right edge, and sitting somewhere in the middle between two people. It tests your ability to write clean, localized sliding window logic without complicated math.

Algorithmic pattern used

This problem relies on a Two Pointers (Sliding Window) or Gap Counting pattern. You iterate through the array to find the gaps of 0s between 1s.

1. If the gap is at the very beginning (from index 0 to the first 1), the maximum distance is exactly the size of the gap.
2. If the gap is at the very end (from the last 1 to the end of the array), the maximum distance is also exactly the size of the gap.
3. If the gap is bounded by two 1s in the middle, the optimal seat is in the exact center of the gap. The distance to the closest person is gap_length / 2 (or more specifically, (right_index - left_index) / 2). You return the maximum of these three scenarios.

Example explanation

Seats: [1, 0, 0, 0, 1, 0, 1]

• First 1 is at index 0. No left gap.
• Next 1 is at index 4. The gap of zeroes is [1, 2, 3]. Length is 4 - 0 = 4. Middle distance = 4 / 2 = 2. (If we sit at index 2, distance to 0 is 2, distance to 4 is 2).
• Next 1 is at index 6. Gap of zeroes is [5]. Middle distance = (6 - 4) / 2 = 1.
• The array ends at index 6. There is no right gap. The maximum distance we found is 2.

Let's look at [0, 0, 1, 0].

• Left gap (before index 2): length 2. Distance if we sit at 0 is 2.
• Right gap (after index 2): length 1. Distance if we sit at 3 is 1. Max distance is 2.

Common mistakes candidates make

The most common mistake is applying the gap / 2 logic to the beginning and end of the array. If you have [0, 0, 0, 1], and you sit at index 0, your distance is 3! If you apply the middle formula, you might divide it by 2 and return 1, which is entirely wrong. You must explicitly track the first 1 and last 1 to handle the boundaries.

Interview preparation tip

For the Maximize Distance to Closest Person coding problem, the cleanest way to write the code is to maintain a prev variable tracking the index of the last seen 1 (initialized to -1). When iterating, if you see a 1, handle the left edge case if prev == -1, and the middle case if prev != -1. After the loop, handle the right edge case using n - 1 - prev. This structure guarantees no edge case is forgotten.