Maximize Distance to Closest Person - Solution & Explanation
Problem Statement
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]is0or1.- At least one seat is empty.
- At least one seat is occupied.
Approach Overview
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 1: Two-Pass or Left-Right Scan
In this approach, you perform a left-to-right scan to compute the distance to the nearest occupied seat on the left and a right-to-left scan to compute the distance to the nearest occupied seat on the right. For each empty seat, the result will be the minimum of these distances. The final solution is the maximum among these minimum distances.
The C solution uses two arrays to keep track of the minimum distances to the nearest person on the left and right. It initializes two separate passes over the seats array: the first pass computes the distance to the last occupied chair on the left, while the second pass computes the distance to the next occupied chair on the right. Finally, it calculates the maximum of the minimum distances for each seat.
Complexity
Time Complexity: O(n) where n is the number of seats. We pass over the list twice.
Space Complexity: O(n) due to the use of additional arrays for storing distances.
Approach 2: Single-Pass Using Two Pointers
This approach involves using a single pass over the seats array while utilizing two pointers. The first pointer stores the last filled seat position, and with each empty seat, the calculation is made based on its distance from the last filled position and the subsequent fill.
In this C solution, a single pass evaluates each seat while dynamically adjusting two pointers (prev for the last occupied position and future for the next occupied position) to compute potential seat distances.
Complexity
Time Complexity: O(n) for a single traversal.
Space Complexity: O(1) since it uses a constant amount of space.
Approach 3: Single Traversal
We define two variables first and 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.
Then, we traverse the array seats. If the current position is occupied, and if last has been updated before, it means there was someone before, so we update d = max(d, i - last). If first has not been updated before, it means there was no one before, so we update first = i. Next, we update last = i.
Finally, we return max(first, n - last - 1, d / 2).
The time complexity is O(n), where n is the length of the array seats. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pass or Left-Right Scan | Time Complexity: O(n) where n is the number of seats. We pass over the list twice. |
| Single-Pass Using Two Pointers | Time Complexity: O(n) for a single traversal. |
| Single Traversal | — |
Detailed Complexity Analysis
| 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 |
Video Solution
maximize distance to closest person leetcode | leetcode 849 | array • Naresh Gupta • 6,517 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximize Distance to Closest Person easy or hard?
Maximize Distance to Closest Person Python/Java solution
How to solve Maximize Distance to Closest Person in O(n)?
What is the best approach for Maximize Distance to Closest Person?
Is Maximize Distance to Closest Person asked at Google/Amazon/Meta?
What data structure is used in Maximize Distance to Closest Person?
What is the time complexity of Maximize Distance to Closest Person?
Ready to solve this problem?
Practice Maximize Distance to Closest Person with our built-in code editor and test cases.
Practice on FleetCode