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

Roblox Samsung Snowflake Tinkoff

Prompt

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the i^th seat, and seats[i] = 0 represents that the i^th 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 * 10⁴
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.

1class Solution {2    public int maxDistToClosest(int[] seats) {3        int n = seats.length;4        int maxDistance = 0;5        for (int i = 0; i < n; i++) {6            if (seats[i] == 0) {7                // Find closest person to the left8                int leftDist = n; // Initialize with a large value9                for (int j = i - 1; j >= 0; j--) {10                    if (seats[j] == 1) {11                        leftDist = i - j;12                        break;13                    }14                }15                16                // Find closest person to the right17                int rightDist = n; // Initialize with a large value18                for (int j = i + 1; j < n; j++) {19                    if (seats[j] == 1) {20                        rightDist = j - i;21                        break;22                    }23                }24                25                int currentMinDist = Math.min(leftDist, rightDist);26                maxDistance = Math.max(maxDistance, currentMinDist);27            }28        }29        return maxDistance;30    }31}

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.

This approach improves upon the brute-force method by pre-calculating the distances to the nearest person on the left and right for every seat. We use two auxiliary arrays for this purpose, which allows us to find the answer in a linear number of passes.

Algorithm

Create an integer array left of size n.
Initialize a distance variable dist to a large value (e.g., n).
Iterate from i = 0 to n-1:
- If seats[i] == 1, reset dist = 0.
- Else, increment dist.
- Set left[i] = dist.
Create an integer array right of size n.
Reset dist to a large value.
Iterate from i = n-1 down to 0:
- If seats[i] == 1, reset dist = 0.
- Else, increment dist.
- Set right[i] = dist.
Initialize max_dist = 0.
Iterate from i = 0 to n-1:
- If seats[i] == 0, calculate current_dist = min(left[i], right[i]).
- Update max_dist = max(max_dist, current_dist).
Return max_dist.

Walkthrough

Instead of repeatedly scanning for the nearest person for each empty seat, we can precompute this information. We use two passes and two auxiliary arrays, left and right.

Left Pass: We create an array left where left[i] stores the distance from seat i to the nearest person on its left. We populate this by iterating from left to right. If seats[i] has a person, left[i] is 0. Otherwise, left[i] is left[i-1] + 1.
Right Pass: Similarly, we create an array right where right[i] stores the distance to the nearest person on its right. We populate this by iterating from right to left.
Final Pass: With left and right arrays computed, we iterate through the seats one last time. For each empty seat i, the distance to the closest person is simply min(left[i], right[i]). We find the maximum of these minimums over all empty seats.

1class Solution {2    public int maxDistToClosest(int[] seats) {3        int n = seats.length;4        int[] left = new int[n];5        int[] right = new int[n];6        7        // Fill left array8        int dist = n; // Represents infinity9        for (int i = 0; i < n; i++) {10            if (seats[i] == 1) {11                dist = 0;12            } else {13                dist++;14            }15            left[i] = dist;16        }17        18        // Fill right array19        dist = n; // Represents infinity20        for (int i = n - 1; i >= 0; i--) {21            if (seats[i] == 1) {22                dist = 0;23            } else {24                dist++;25            }26            right[i] = dist;27        }28        29        // Find the maximum of the minimums30        int maxDistance = 0;31        for (int i = 0; i < n; i++) {32            if (seats[i] == 0) {33                maxDistance = Math.max(maxDistance, Math.min(left[i], right[i]));34            }35        }36        37        return maxDistance;38    }39}

Complexity

Time

O(N). We perform three separate passes over the array (one for `left`, one for `right`, and one for the final calculation), each taking O(N) time. This simplifies to O(N).

Space

O(N), as we use two auxiliary arrays, `left` and `right`, each of size N.

Trade-offs

Pros

Much faster than the brute-force approach with a linear time complexity.
The logic is still relatively straightforward, breaking the problem down into smaller, manageable passes.

Cons

Requires extra space proportional to the input size, which might be a concern for very large inputs.

The most efficient approach solves the problem in a single pass with constant extra space. The key insight is that the maximum distance can only occur in one of three scenarios: an empty block of seats at the beginning, an empty block at the end, or an empty block between two people. We can calculate the maximum distance for each of these cases as we iterate through the array.

Algorithm

Initialize max_dist = 0 and last_person_index = -1.
Loop through each seat i from 0 to n-1.
If seats[i] == 1:
- If last_person_index == -1 (this is the first person found), the maximum distance is i (for sitting at seats[0]).
- Else, there is a gap of empty seats between last_person_index and i. The best place to sit is in the middle, at a distance of (i - last_person_index) / 2 from either person. Update max_dist with this value if it's larger.
- Update last_person_index = i.
After the loop, handle the case of trailing empty seats. The distance from the end of the row to the last person is n - 1 - last_person_index. Update max_dist with this value if it's larger.
Return max_dist.

Walkthrough

We can optimize to a single pass by realizing that the problem is about finding the largest gap of empty seats. We can iterate through the seats, keeping track of the index of the last person we've seen (lastPersonIndex).

Gaps between people: When we are at index i and find a person (seats[i] == 1), and we have seen a person before at lastPersonIndex, the number of empty seats between them is i - lastPersonIndex - 1. The best place to sit in this gap is in the middle, which gives a maximum distance of (i - lastPersonIndex) / 2 to the nearest person. We update our global maximum distance with this value.
Leading empty seats: If we find the first person at index i, it means seats 0 to i-1 were empty. The best place to sit is at index 0, giving a distance of i. This is a special case we handle when we find the very first person.
Trailing empty seats: After the loop finishes, we need to account for any empty seats at the end of the row. The distance from the last person at lastPersonIndex to the end of the row (n-1) is n - 1 - lastPersonIndex. This is another potential maximum.

By tracking lastPersonIndex and updating the max distance as we find each person, we can solve the problem in one pass.

1class Solution {2    public int maxDistToClosest(int[] seats) {3        int n = seats.length;4        int maxDistance = 0;5        int lastPersonIndex = -1;6 7        for (int i = 0; i < n; i++) {8            if (seats[i] == 1) {9                if (lastPersonIndex == -1) {10                    // Case: leading zeros. Alex sits at index 0.11                    maxDistance = i;12                } else {13                    // Case: zeros between two people. Alex sits in the middle.14                    maxDistance = Math.max(maxDistance, (i - lastPersonIndex) / 2);15                }16                lastPersonIndex = i;17            }18        }19 20        // Case: trailing zeros. Alex sits at the last seat.21        if (lastPersonIndex != n - 1) {22            maxDistance = Math.max(maxDistance, n - 1 - lastPersonIndex);23        }24 25        return maxDistance;26    }27}

Complexity

Time

O(N), as we iterate through the array only once.

Space

O(1), as we only use a few variables to keep track of the last person's index and the maximum distance.

Trade-offs

Pros

Optimal time complexity of O(N).
Optimal space complexity of O(1).

Cons

The logic can be slightly more complex to reason about initially, as it combines multiple cases (leading, middle, and trailing gaps) into a single pass.

Solutions

Solution

1class Solution {2public3  int maxDistToClosest(int[] seats) {4    int first = -1, last = -1;5    int d = 0, n = seats.length;6    for (int i = 0; i < n; ++i) {7      if (seats[i] == 1) {8        if (last != -1) {9          d = Math.max(d, i - last);10        }11        if (first == -1) {12          first = i;13        }14        last = i;15      }16    }17    return Math.max(d / 2, Math.max(first, n - last - 1));18  }19}

1class Solution {2public:3  int maxDistToClosest(vector<int> &seats) {4    int first = -1, last = -1;5    int d = 0, n = seats.size();6    for (int i = 0; i < n; ++i) {7      if (seats[i] == 1) {8        if (last != -1) {9          d = max(d, i - last);10        }11        if (first == -1) {12          first = i;13        }14        last = i;15      }16    }17    return max({d / 2, max(first, n - last - 1)});18  }19};

1class Solution:2    def maxDistToClosest(self, seats: List[int]) -> int: first = last = None d = 0 for i, c in enumerate(seats): if c: if last is not None: d = max(d, i - last) if first is None: first = i last = i return max(first, len(seats) - last - 1, d // 2)

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 problem

Solution

1class Solution {2public3  int maxDistToClosest(int[] seats) {4    int first = -1, last = -1;5    int d = 0, n = seats.length;6    for (int i = 0; i < n; ++i) {7      if (seats[i] == 1) {8        if (last != -1) {9          d = Math.max(d, i - last);10        }11        if (first == -1) {12          first = i;13        }14        last = i;15      }16    }17    return Math.max(d / 2, Math.max(first, n - last - 1));18  }19}

1class Solution {2public:3  int maxDistToClosest(vector<int> &seats) {4    int first = -1, last = -1;5    int d = 0, n = seats.size();6    for (int i = 0; i < n; ++i) {7      if (seats[i] == 1) {8        if (last != -1) {9          d = max(d, i - last);10        }11        if (first == -1) {12          first = i;13        }14        last = i;15      }16    }17    return max({d / 2, max(first, n - last - 1)});18  }19};

1class Solution:2    def maxDistToClosest(self, seats: List[int]) -> int: first = last = None d = 0 for i, c in enumerate(seats): if c: if last is not None: d = max(d, i - last) if first is None: first = i last = i return max(first, len(seats) - last - 1, d // 2)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.