Maximize Distance to Closest Person solution and explanation
Google
9 more videos on this problem
maximize distance to closest person leetcode | leetcode 849 | arrayNaresh Gupta · 9:45 · 6K views
Maximize Distance to Closest Person | Live Coding with Explanation | Leetcode - 849Algorithms Made Easy · 7:20 · 3K views
Leetcode - Maximize Distance to Closest Person (Python)Timothy H Chang · 9:22 · 2K views
Maximize Distance to Closest Person | Leetcode 849 | Live coding session 🔥🔥 | Arrays 💯Coding Decoded · 11:07 · 2K views
Maximize Distance to Closest Person | Leet code 849 | Theory explained + Python codeSai Anish Malla · 14:47 · 1K views
GOOGLE | LEETCODE 849: MAXIMIZE DISTANCE TO CLOSEST PERSON | Solution Explained | C++Nikash Kumar · 8:33 · 1K views
849. Maximize Distance to Closest Person | LEETCODE MEDIUMcode Explainer · 9:38 · 949 views
849. Maximize Distance to Closest Person(Leetcode Problem)viralSongs · 5:34 · 740 views
Maximize Distance to Closest Person Leetcode | Leetcode 849 | One pass solution O(N)Code Bashers · 13:02 · 615 views
GOOGLE | LEETCODE 849: MAXIMIZE DISTANCE TO CLOSEST PERSON | CODE | C++Nikash Kumar · 3:41 · 587 views
The problem
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.
from typing import List
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
n = len(seats)
left = [n] * n
right = [n] * n
for i in range(n):
if seats[i] == 1:
left[i] = 0
elif i > 0:
left[i] = left[i-1] + 1
for i in range(n-1, -1, -1):
if seats[i] == 1:
right[i] = 0
elif i < n - 1:
right[i] = right[i+1] + 1
return max(min(left[i], right[i]) for i in range(n) if seats[i] == 0)
# Example usage
sol = Solution()
seats = [1, 0, 0, 0, 1, 0, 1]
print(sol.maxDistToClosest(seats))import java.util.Arrays;
public class MaxDistance {
public int maxDistToClosest(int[] seats) {
int n = seats.length;
int[] left = new int[n], right = new int[n];
Arrays.fill(left, n);
Arrays.fill(right, n);
for (int i = 0, last = -1; i < n; ++i) {
if (seats[i] == 1) last = i;
else if (last != -1) left[i] = i - last;
}
for (int i = n - 1, last = -1; i >= 0; --i) {
if (seats[i] == 1) last = i;
else if (last != -1) right[i] = last - i;
}
int maxDist = 0;
for (int i = 0; i < n; ++i) {
if (seats[i] == 0) {
maxDist = Math.max(maxDist, Math.min(left[i], right[i]));
}
}
return maxDist;
}
public static void main(String[] args) {
MaxDistance solution = new MaxDistance();
int[] seats = {1, 0, 0, 0, 1, 0, 1};
System.out.println(solution.maxDistToClosest(seats));
}
}#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int n = seats.size();
vector<int> left(n, n), right(n, n);
// Left to right pass
for (int i = 0, last = -1; i < n; ++i) {
if (seats[i] == 1) last = i;
else if (last != -1) left[i] = i - last;
}
// Right to left pass
for (int i = n - 1, last = -1; i >= 0; --i) {
if (seats[i] == 1) last = i;
else if (last != -1) right[i] = last - i;
}
// Calculate max of min distances
int maxDist = 0;
for (int i = 0; i < n; ++i) {
if (seats[i] == 0) {
int dist = min(left[i], right[i]);
maxDist = max(maxDist, dist);
}
}
return maxDist;
}
};
int main() {
vector<int> seats = {1, 0, 0, 0, 1, 0, 1};
Solution sol;
cout << sol.maxDistToClosest(seats) << endl;
return 0;
}function maxDistToClosest(seats) {
const n = seats.length;
const left = new Array(n).fill(n);
const right = new Array(n).fill(n);
for (let i = 0, last = -1; i < n; i++) {
if (seats[i] === 1) last = i;
else if (last !== -1) left[i] = i - last;
}
for (let i = n - 1, last = -1; i >= 0; i--) {
if (seats[i] === 1) last = i;
else if (last !== -1) right[i] = last - i;
}
let maxDist = 0;
for (let i = 0; i < n; i++) {
if (seats[i] === 0) {
const dist = Math.min(left[i], right[i]);
maxDist = Math.max(maxDist, dist);
}
}
return maxDist;
}
// Example usage
console.log(maxDistToClosest([1, 0, 0, 0, 1, 0, 1]));#include <stdio.h>
int maxDistToClosest(int* seats, int seatsSize) {
int left[seatsSize];
int right[seatsSize];
int maxDist = 0;
// Left to right pass
int lastFilled = -1;
for (int i = 0; i < seatsSize; i++) {
if (seats[i] == 1) {
lastFilled = i;
left[i] = 0;
} else {
left[i] = (lastFilled == -1) ? seatsSize : i - lastFilled;
}
}
// Right to left pass
lastFilled = -1;
for (int i = seatsSize - 1; i >= 0; i--) {
if (seats[i] == 1) {
lastFilled = i;
right[i] = 0;
} else {
right[i] = (lastFilled == -1) ? seatsSize : lastFilled - i;
}
}
// Calculate max of min distances
for (int i = 0; i < seatsSize; i++) {
if (seats[i] == 0) {
int distance = (left[i] < right[i]) ? left[i] : right[i];
if (distance > maxDist) maxDist = distance;
}
}
return maxDist;
}
int main() {
int seats[] = {1,0,0,0,1,0,1};
int size = sizeof(seats) / sizeof(seats[0]);
printf("%d\n", maxDistToClosest(seats, size));
return 0;
}using System;
public class Solution {
public int MaxDistToClosest(int[] seats) {
int n = seats.Length;
int[] left = new int[n];
int[] right = new int[n];
for (int i = 0, last = -1; i < n; ++i) {
if (seats[i] == 1) last = i;
else left[i] = (last == -1) ? n : i - last;
}
for (int i = n - 1, last = -1; i >= 0; --i) {
if (seats[i] == 1) last = i;
else right[i] = (last == -1) ? n : last - i;
}
int maxDist = 0;
for (int i = 0; i < n; ++i) {
if (seats[i] == 0) {
maxDist = Math.Max(maxDist, Math.Min(left[i], right[i]));
}
}
return maxDist;
}
public static void Main(string[] args) {
int[] seats = { 1, 0, 0, 0, 1, 0, 1 };
Solution sol = new Solution();
Console.WriteLine(sol.MaxDistToClosest(seats));
}
}The Python solution takes a slightly different approach to handling the calculations within the same loop for each direction and uses list comprehensions to calculate the maximum of the minimal distances.
Time Complexity: O(n) for the two passes.
Space Complexity: O(n) for the left and right distance arrays.
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.
from typing import List
class Solution:
def maxDistToClosest(self, seats: List[int]) -> int:
prev = -1
future = 0
maxDist = 0
for i in range(len(seats)):
if seats[i] == 1:
prev = i
else:
while future < len(seats) and (seats[future] == 0 or future < i):
future += 1
leftDist = len(seats) if prev == -1 else i - prev
rightDist = len(seats) if future == len(seats) else future - i
maxDist = max(maxDist, min(leftDist, rightDist))
return maxDist
# Example usage
sol = Solution()
seats = [1, 0, 0, 0, 1, 0, 1]
print(sol.maxDistToClosest(seats))public class MaxDistanceToClosest {
public int maxDistToClosest(int[] seats) {
int prev = -1, future = 0, maxDist = 0;
for (int i = 0; i < seats.length; ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < seats.length && (seats[future] == 0 || future < i)) {
future++;
}
int leftDist = (prev == -1) ? seats.length : i - prev;
int rightDist = (future == seats.length) ? seats.length : future - i;
int minDist = Math.min(leftDist, rightDist);
maxDist = Math.max(maxDist, minDist);
}
}
return maxDist;
}
public static void main(String[] args) {
MaxDistanceToClosest sol = new MaxDistanceToClosest();
int[] seats = {1, 0, 0, 0, 1, 0, 1};
System.out.println(sol.maxDistToClosest(seats));
}
}#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int prev = -1, future = 0, maxDist = 0;
for (int i = 0; i < seats.size(); ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < seats.size() && (seats[future] == 0 || future < i)) {
++future;
}
int leftDist = (prev == -1) ? seats.size() : i - prev;
int rightDist = (future == seats.size()) ? seats.size() : future - i;
int minDist = min(leftDist, rightDist);
maxDist = max(maxDist, minDist);
}
}
return maxDist;
}
};
int main() {
vector<int> seats = {1, 0, 0, 0, 1, 0, 1};
Solution sol;
cout << sol.maxDistToClosest(seats) << endl;
return 0;
}function maxDistToClosest(seats) {
let prev = -1, future = 0, maxDist = 0;
const n = seats.length;
for (let i = 0; i < n; ++i) {
if (seats[i] === 1) {
prev = i;
} else {
while (future < n && (seats[future] === 0 || future < i)) {
future++;
}
const leftDist = prev === -1 ? n : i - prev;
const rightDist = future === n ? n : future - i;
const minDist = Math.min(leftDist, rightDist);
maxDist = Math.max(maxDist, minDist);
}
}
return maxDist;
}
// Example usage
console.log(maxDistToClosest([1, 0, 0, 0, 1, 0, 1]));#include <stdio.h>
int maxDistToClosest(int* seats, int seatsSize) {
int prev = -1;
int future = 0;
int maxDist = 0;
for (int i = 0; i < seatsSize; ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < seatsSize && seats[future] == 0 || future < i) {
future++;
}
int leftDist = (prev == -1) ? seatsSize : i - prev;
int rightDist = (future == seatsSize) ? seatsSize : future - i;
int minDist = (leftDist < rightDist) ? leftDist : rightDist;
if (minDist > maxDist) maxDist = minDist;
}
}
return maxDist;
}
int main() {
int seats[] = {1,0,0,0,1,0,1};
int size = sizeof(seats) / sizeof(seats[0]);
printf("%d\n", maxDistToClosest(seats, size));
return 0;
}using System;
public class Solution {
public int MaxDistToClosest(int[] seats) {
int prev = -1, future = 0, maxDist = 0;
for (int i = 0; i < seats.Length; ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < seats.Length && (seats[future] == 0 || future < i)) {
future++;
}
int leftDist = (prev == -1) ? seats.Length : i - prev;
int rightDist = (future == seats.Length) ? seats.Length : future - i;
int minDist = Math.Min(leftDist, rightDist);
maxDist = Math.Max(maxDist, minDist);
}
}
return maxDist;
}
public static void Main(string[] args) {
int[] seats = { 1, 0, 0, 0, 1, 0, 1 };
Solution sol = new Solution();
Console.WriteLine(sol.MaxDistToClosest(seats));
}
}This Python implementation walks through the seats list a single time, maintaining pointers to quickly calculate the closest occupied seat distances while navigating through empty seats.
Time Complexity: O(n)
Space Complexity: O(1)
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).
function maxDistToClosest(seats: number[]): number {
let first = -1,
last = -1;
let d = 0,
n = seats.length;
for (let i = 0; i < n; ++i) {
if (seats[i] === 1) {
if (last !== -1) {
d = Math.max(d, i - last);
}
if (first === -1) {
first = i;
}
last = i;
}
}
return Math.max(first, n - last - 1, d >> 1);
}func maxDistToClosest(seats []int) int {
first, last := -1, -1
d := 0
for i, c := range seats {
if c == 1 {
if last != -1 {
d = max(d, i-last)
}
if first == -1 {
first = i
}
last = i
}
}
return max(d/2, max(first, len(seats)-last-1))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pass or Left-Right Scan | Time Complexity: O(n) for the two passes. |
| Single-Pass Using Two Pointers | Time Complexity: O(n) |
| Single Traversal | – |
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 |
Frequently asked questions
Is Maximize Distance to Closest Person easy or hard?
Maximize Distance to Closest Person is generally classified as a Medium problem. The main challenge is correctly handling three cases: gaps between occupied seats, leading empty seats, and trailing empty seats. Once the gap-based insight is clear, the implementation becomes straightforward.
Maximize Distance to Closest Person Python/Java solution
In Python or Java, iterate through the array while tracking the previous index containing 1. Update the maximum distance for each zero segment and handle edges separately. The algorithm is identical across languages and runs in O(n) time with O(1) space.
How to solve Maximize Distance to Closest Person in O(n)?
Scan the array while tracking the index of the last occupied seat. For each new occupied seat, compute the midpoint distance of the zero segment between them. Also handle leading and trailing zero segments separately. This single traversal guarantees O(n) time and constant O(1) extra space.
What is the best approach for Maximize Distance to Closest Person?
The best approach is a single-pass greedy scan that analyzes gaps between occupied seats. Track the previous occupied seat and compute the maximum distance for middle gaps, leading zeros, and trailing zeros. This solution runs in O(n) time and O(1) space, making it the optimal approach for interviews.
Is Maximize Distance to Closest Person asked at Google/Amazon/Meta?
Maximize Distance to Closest Person is a common array and greedy interview problem frequently reported in interviews at large tech companies including Amazon, Google, and Meta. It tests reasoning about gaps in arrays, edge handling, and optimizing space usage.
What data structure is used in Maximize Distance to Closest Person?
The problem primarily uses an array as the input data structure. Some solutions also use auxiliary arrays to store nearest distances from the left and right. The optimized solution avoids extra structures and only tracks indices while scanning the array.
What is the time complexity of Maximize Distance to Closest Person?
The optimal solutions run in O(n) time where n is the number of seats. Both the two-pass distance scan and the single-pass gap analysis traverse the array linearly. Space complexity is O(n) for the two-pass method and O(1) for the optimized single-pass approach.