Maximize Distance to Closest Person — Problem & Solution
Maximize Distance to Closest Person solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximize Distance to Closest Person is a medium coding problem on arrays and two pointers, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Two Pointers
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A row of seats is given as an array seats, where seats[i] = 1 means seat i is taken and seats[i] = 0 means it is empty. At least one seat is empty and at least one is taken.
Alex wants to sit in an empty seat that is as far as possible from the nearest person. Return that largest possible distance to the closest person.
Example 1
Input: seats = [0,0,1,0,0,0,0,0,1]
Output: 3
Explanation: In the middle gap of five empty seats, the centre seat (index 5) is 3 away from both neighbours. The leading gap only gives 2.
Example 2
Input: seats = [1,0,0,0,0]
Output: 4
Explanation: The last seat is 4 away from the only person.
Example 3
Input: seats = [1,0]
Output: 1
Constraints
2 <= seats.length <= 2 * 10^4seats[i] is 0 or 1At least one seat is emptyAt least one seat is occupied
Hints for Maximize Distance to Closest Person
Hint 1
The empty seats form gaps between people. Treat a gap between two people differently from a gap at either end of the row.
Hint 2
In an interior gap of
kempty seats, the best seat is in the middle, at distance(k + 1) / 2(integer division).Hint 3
At the ends there is nobody on one side, so a leading or trailing gap of
kseats gives distancek.
How to solve Maximize Distance to Closest Person
Only the lengths of the runs of empty seats matter: an interior run of k seats offers ceil(k / 2), and a run touching either end of the row offers k.
Approach
- Find the first and last occupied seats
firstandlast. - Start with
best = max(first, n - 1 - last)— the edge gaps. - Walk the occupied seats in order; for consecutive people at
pandq, updatebest = max(best, (q - p) / 2). - Return
best.
Why it works
For a seat in an interior gap between people at p and q, the distance to the closest person is min(i - p, q - i), maximised at the middle with value floor((q - p) / 2), which equals ceil(k / 2) for k = q - p - 1 empty seats. In an edge gap only one person is near, so the far end of the gap is best, at distance equal to the gap length.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Edge gaps are not halved:
[1,0,0,0,0]answers 4, not 2. - For an interior gap use the distance between the two people,
(q - p) / 2, not the number of empty seats divided by two.
Reference solution
Python
from typing import List
def maxDistToClosest(seats: List[int]) -> int:
n = len(seats)
prev = -1
best = 0
for i, s in enumerate(seats):
if s == 1:
best = max(best, i if prev < 0 else (i - prev) // 2)
prev = i
return max(best, n - 1 - prev)Java
public static int maxDistToClosest(int[] seats) {
int n = seats.length, prev = -1, best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] != 1) continue;
best = Math.max(best, prev < 0 ? i : (i - prev) / 2);
prev = i;
}
return Math.max(best, n - 1 - prev);
}C++
int maxDistToClosest(vector<int>& seats) {
int n = seats.size(), prev = -1, best = 0;
for (int i = 0; i < n; i++) {
if (seats[i] != 1) continue;
best = max(best, prev < 0 ? i : (i - prev) / 2);
prev = i;
}
return max(best, n - 1 - prev);
}JavaScript
var maxDistToClosest = function(seats) {
var n = seats.length, prev = -1, best = 0;
for (var i = 0; i < n; i++) {
if (seats[i] !== 1) continue;
best = Math.max(best, prev < 0 ? i : Math.floor((i - prev) / 2));
prev = i;
}
return Math.max(best, n - 1 - prev);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique