Maximize Distance to Closest Person
Asked at Adobe
Problem
You are given an array seats where seats[i] = 1 represents a person sitting in the i-th seat and seats[i] = 0 represents an empty seat. There is at least one empty seat and at least one person sitting. Find the maximum distance to the closest person from any empty seat. The distance is the number of seats between them.
Asked At
| Company | Difficulty | |
|---|---|---|
| Adobe | MEDIUM | View all Adobe questions → |
How to Think About It
Brute force: for each empty seat, scan left and right to find the nearest occupied seat, and track the maximum distance.
Optimize with a single pass by tracking the last occupied seat seen so far.
Handle three cases: empty seats before the first person, empty seats between two people, and empty seats after the last person.
For leading/trailing empty seats, the distance is the count of consecutive zeros from the edge.
For empty seats between two people, the distance to the closest person is half the gap (integer division).
Optimal Approach
Track the index of the last person seen. For leading zeros, set last to -1 so the distance calculation works correctly. For each empty seat, compute the distance to the nearest person by considering both the previous person (last) and the next person (found by looking ahead). Alternatively, do two passes: one left-to-right recording the distance to the nearest person on the left, and one right-to-left for the nearest on the right, taking the minimum at each seat. O(n) time, O(1) space.
What Trips People Up in Real Interviews
Clarify: seats are a straight row, not circular — edge seats only have one neighbor.
Edge case: [1,0,0,0] — the closest person is at index 0, answer is 3.
Edge case: [0,0,1] — closest person is at index 2, answer is 2.
Edge case: [0,1,0,0,1,0] — the middle empty seat between two people at distance 2 from each, answer is 2.
The problem can also be solved with two passes (left-to-right then right-to-left) which is cleaner for interviews.
Solution Code
def maxDistToClosest(seats):
n = len(seats)
last = -1
result = 0
for i in range(n):
if seats[i] == 1:
if last == -1:
result = max(result, i)
else:
result = max(result, (i - last) // 2)
last = i
result = max(result, n - 1 - last)
return resultFrequently Asked Questions
What is the Maximize Distance to Closest Person problem?
You are given an array seats where seats[i] = 1 represents a person sitting in the i-th seat and seats[i] = 0 represents an empty seat. There is at least one empty seat and at least one person sitting. Find the maximum distance to the closest person from any empty seat. The distance is the number of seats between them.
How do you solve Maximize Distance to Closest Person?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Maximize Distance to Closest Person?
Maximize Distance to Closest Person is asked at Adobe. It is a medium difficulty problem.
What are common mistakes on Maximize Distance to Closest Person?
- Clarify: seats are a straight row, not circular — edge seats only have one neighbor.
- Edge case: [1,0,0,0] — the closest person is at index 0, answer is 3.
- Edge case: [0,0,1] — closest person is at index 2, answer is 2.
- Edge case: [0,1,0,0,1,0] — the middle empty seat between two people at distance 2 from each, answer is 2.
- The problem can also be solved with two passes (left-to-right then right-to-left) which is cleaner for interviews.