Maximize Distance to Closest Person
Maximize Distance to Closest Person is a medium arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (one pass over the gaps), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (search outward from every empty seat) up.
Problem
A row of seats is described by the array seats, where seats[i] = 1 means seat i is taken and seats[i] = 0 means it is free. There is at least one free seat and at least one taken seat.
You want to sit in a free seat so that the distance to the closest person is as large as possible. The distance between seats i and j is |i - j|. Return that largest possible distance.
Examples
Example 1
- Input
seats = [1, 0, 0, 0, 0, 1, 0, 1]- Output
2- Why
- Sitting at index 2 or 3 leaves a gap of 2 to the nearest person; no seat does better.
Example 2
- Input
seats = [0, 0, 0, 1, 0]- Output
3- Why
- Index 0 is at the open left end, 3 seats away from the only person.
Example 3
- Input
seats = [1, 0]- Output
1- Why
- The only free seat is right next to the occupied one.
Constraints
2 <= seats.length <= 2 * 10^4seats[i]is0or1.- At least one seat is empty and at least one seat is taken.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (search outward from every empty seat) | O(n²) | O(1) |
| Optimal (one pass over the gaps) | O(n) | O(1) |
1Brute force (search outward from every empty seat)
O(n²)Each empty seat may scan most of the row.O(1)Only a few indices.For every empty seat, walk left and right until a person is found, take the smaller of the two distances, and keep the maximum over all empty seats.
- For each i with seats[i] == 0:
- Find the nearest j < i with seats[j] == 1 and the nearest k > i with seats[k] == 1 (either may not exist).
- dist = min of the existing distances; best = max(best, dist).
- Return best.
class Solution {
public int maxDistToClosest(int[] seats) {
int n = seats.length, best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) continue;
int dist = Integer.MAX_VALUE;
for (int j = i - 1; j >= 0; j--) {
if (seats[j] == 1) {
dist = i - j;
break;
}
}
for (int k = i + 1; k < n; k++) {
if (seats[k] == 1) {
dist = Math.min(dist, k - i);
break;
}
}
best = Math.max(best, dist);
}
return best;
}
}class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
n = len(seats)
best = 0
for i in range(n):
if seats[i] == 1:
continue
dist = float("inf")
for j in range(i - 1, -1, -1):
if seats[j] == 1:
dist = i - j
break
for k in range(i + 1, n):
if seats[k] == 1:
dist = min(dist, k - i)
break
best = max(best, dist)
return bestclass Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int n = seats.size(), best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) continue;
int dist = INT_MAX;
for (int j = i - 1; j >= 0; j--) {
if (seats[j] == 1) {
dist = i - j;
break;
}
}
for (int k = i + 1; k < n; k++) {
if (seats[k] == 1) {
dist = min(dist, k - i);
break;
}
}
best = max(best, dist);
}
return best;
}
};function maxDistToClosest(seats) {
const n = seats.length;
let best = 0;
for (let i = 0; i < n; i++) {
if (seats[i] === 1) continue;
let dist = Infinity;
for (let j = i - 1; j >= 0; j--) {
if (seats[j] === 1) {
dist = i - j;
break;
}
}
for (let k = i + 1; k < n; k++) {
if (seats[k] === 1) {
dist = Math.min(dist, k - i);
break;
}
}
best = Math.max(best, dist);
}
return best;
}2Optimal (one pass over the gaps)
O(n)A single left-to-right scan.O(1)Two integers.Remember the index of the previous person. Each time you meet a person at i: if there was no previous person, the leading empty run gives distance i; otherwise the gap between them gives (i - prev) / 2. After the scan, the trailing run gives n - 1 - prev. The answer is the largest of these.
- prev = -1, best = 0.
- For each i with seats[i] == 1: best = max(best, prev == -1 ? i : (i - prev) / 2); prev = i.
- best = max(best, n - 1 - prev).
- Return best.
class Solution {
public int maxDistToClosest(int[] seats) {
int n = seats.length, prev = -1, best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) {
best = Math.max(best, prev == -1 ? i : (i - prev) / 2);
prev = i;
}
}
return Math.max(best, n - 1 - prev);
}
}class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
n = len(seats)
prev = -1
best = 0
for i, x in enumerate(seats):
if x == 1:
best = max(best, i if prev == -1 else (i - prev) // 2)
prev = i
return max(best, n - 1 - prev)class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int n = seats.size(), prev = -1, best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] == 1) {
best = max(best, prev == -1 ? i : (i - prev) / 2);
prev = i;
}
}
return max(best, n - 1 - prev);
}
};function maxDistToClosest(seats) {
const n = seats.length;
let prev = -1, best = 0;
for (let i = 0; i < n; i++) {
if (seats[i] === 1) {
best = Math.max(best, prev === -1 ? i : Math.floor((i - prev) / 2));
prev = i;
}
}
return Math.max(best, n - 1 - prev);
}Edge cases to test
- A run of empty seats at the start or the end: the whole run length counts, not half
- A gap of even length between two people, like [1, 0, 0, 1]
- Only one person in the row
- Only one empty seat
Hints
Hint 1
For each empty seat, the answer is the distance to the nearest 1 on either side.
Hint 2
Between two people at positions i and j, the best seat gives (j - i) / 2.
Hint 3
An empty stretch touching an end of the row is special: there is no person on that side, so you can sit at the very end.
FAQ
What is the best time complexity for Maximize Distance to Closest Person?
Optimal (one pass over the gaps) runs in O(n) time and O(1) extra space. A single left-to-right scan.
Which pattern does Maximize Distance to Closest Person use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Maximize Distance to Closest Person?
Yes. Brute force (search outward from every empty seat) takes O(n²) time and O(1) space. For every empty seat, walk left and right until a person is found, take the smaller of the two distances, and keep the maximum over all empty seats.
Which edge cases should I test for Maximize Distance to Closest Person?
A run of empty seats at the start or the end: the whole run length counts, not half; A gap of even length between two people, like [1, 0, 0, 1]; Only one person in the row; Only one empty seat.