Watch 10 video solutions for Maximize Distance to Closest Person, a medium level problem involving Array. This walkthrough by Naresh Gupta has 6,453 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed).
There is at least one empty seat, and at least one person sitting.
Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.
Return that maximum distance to the closest person.
Example 1:
Input: seats = [1,0,0,0,1,0,1] Output: 2 Explanation: 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 Explanation: 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
Constraints:
2 <= seats.length <= 2 * 104seats[i] is 0 or 1.Problem Overview: You get a binary array where 1 represents an occupied seat and 0 represents an empty one. Choose an empty seat so the distance to the closest person is maximized. Return that maximum possible distance.
Approach 1: Two-Pass or Left-Right Scan (O(n) time, O(n) space)
This approach computes the distance to the nearest occupied seat from both directions. Create two arrays: left[i] stores the distance from seat i to the nearest 1 on the left, and right[i] stores the distance to the nearest 1 on the right. Run one pass left-to-right to fill left, and another pass right-to-left to fill right. For each empty seat, the closest person is min(left[i], right[i]). Track the maximum of these values. The algorithm scans the array twice, giving O(n) time and uses auxiliary arrays for O(n) space. This method is straightforward and easy to reason about because each seat explicitly stores its nearest distances.
Approach 2: Single-Pass Using Two Pointers (O(n) time, O(1) space)
This optimized solution observes that the best seat must lie inside a segment of consecutive zeros. Iterate through the array and track the index of the last occupied seat. When another 1 appears, compute the midpoint distance of the zero segment between them: (current - last) / 2. Edge segments need special handling: the leading zeros before the first 1 and trailing zeros after the last 1. For those, the distance equals the segment length because you can sit at the edge. Maintaining only a few variables makes the algorithm O(n) time with O(1) space. The logic is essentially greedy: always maximize the minimum distance inside each gap.
Both strategies rely on scanning the array and measuring distances between occupied seats. The optimized version also uses ideas similar to two pointers and greedy gap analysis. Instead of storing all distances, it processes segments as they appear and updates the best answer.
Recommended for interviews: The single-pass two-pointer solution. Interviewers expect you to recognize that the answer depends on gaps between occupied seats and the edges of the array. Explaining the two-pass version first shows clear reasoning about nearest distances, while deriving the O(1) space optimization demonstrates strong problem-solving and understanding of array traversal patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Left-Right Distance Scan | O(n) | O(n) | When clarity matters and you want explicit nearest-distance computation |
| Single-Pass Two Pointers / Gap Analysis | O(n) | O(1) | Preferred optimal solution for interviews and memory‑efficient implementations |