Scale Engineer

Maximize Distance to Closest Person

Med
#0803Time: O(N^2), where N is the number of seats. For each of the O(N) empty seats, we might scan the entire array in the worst case to find the nearest left and right person.Space: O(1), as we only use a few variables to store distances and indices.6 companies
Data structures
Array
Companies
RobloxSamsungSnowflakeTinkoff

Prompt

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 * 104
  • seats[i] is 0 or 1.
  • At least one seat is empty.
  • At least one seat is occupied.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves iterating through every empty seat and, for each one, calculating the distance to the nearest person on the left and the nearest person on the right. The minimum of these two distances is the "distance to the closest person" for that specific empty seat. We keep track of the maximum such distance found across all empty seats.

Algorithm

  • Initialize maxDistance to 0.
  • Iterate through the seats array with an index i from 0 to n-1.
  • If seats[i] is 0 (an empty seat):
    • Find the distance to the nearest person on the left, leftDist. Search backwards from i-1 to 0. If no person is found, leftDist is effectively infinite.
    • Find the distance to the nearest person on the right, rightDist. Search forwards from i+1 to n-1. If no person is found, rightDist is effectively infinite.
    • The distance for the current empty seat i is min(leftDist, rightDist).
    • Update maxDistance = max(maxDistance, min(leftDist, rightDist)).
  • After checking all seats, return maxDistance.

Walkthrough

We can solve this problem by checking every possible empty seat. For each empty seat, we need to determine the distance to the closest person. This involves two sub-problems: finding the closest person to the left and finding the closest person to the right. We can do this by scanning leftwards and rightwards from the current empty seat. The smaller of these two distances is the score for that seat. We then iterate through all empty seats, calculate their scores, and return the maximum score found.

class Solution {    public int maxDistToClosest(int[] seats) {        int n = seats.length;        int maxDistance = 0;        for (int i = 0; i < n; i++) {            if (seats[i] == 0) {                // Find closest person to the left                int leftDist = n; // Initialize with a large value                for (int j = i - 1; j >= 0; j--) {                    if (seats[j] == 1) {                        leftDist = i - j;                        break;                    }                }                                // Find closest person to the right                int rightDist = n; // Initialize with a large value                for (int j = i + 1; j < n; j++) {                    if (seats[j] == 1) {                        rightDist = j - i;                        break;                    }                }                                int currentMinDist = Math.min(leftDist, rightDist);                maxDistance = Math.max(maxDistance, currentMinDist);            }        }        return maxDistance;    }}

Complexity

Time

O(N^2), where N is the number of seats. For each of the O(N) empty seats, we might scan the entire array in the worst case to find the nearest left and right person.

Space

O(1), as we only use a few variables to store distances and indices.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space.

Cons

  • Highly inefficient for large inputs due to the O(N^2) time complexity.

Solutions

class Solution {public  int maxDistToClosest(int[] seats) {    int first = -1, last = -1;    int d = 0, n = seats.length;    for (int 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(d / 2, Math.max(first, n - last - 1));  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem