Maximize Distance to Closest Person

Problem Statement

The problem describes an array called seats, each element of which can be either 0 or 1. If seats[i] = 1, it means the i-th seat is occupied, whereas seats[i] = 0 denotes an empty seat. Alex, looking for a seat, aims to sit in such a manner that the distance to the nearest occupied seat is maximized. The task is to compute and return this maximum possible distance to the nearest person from any empty seat that Alex chooses.

Examples

Example 1

Input:

seats = [1,0,0,0,1,0,1]

Output:

2

Explanation:

If Alex sits at index 2, the closest person is at index 0 or 4 (both distance 2). This is the farthest he can be from anyone.

Example 2

Input:

seats = [1,0,0,0]

Output:

3

Explanation:

Alex should sit at the last seat (index 3), where the closest person is 3 seats away.

Example 3

Input:

seats = [0,1]

Output:

1

Explanation:

Alex can sit at index 0, which is 1 seat away from the only person sitting at index 1.

Constraints

• 2 <= seats.length <= 2 * 10^4
• seats[i] is 0 or 1
• At least one seat is empty
• At least one seat is occupied

Approach and Intuition

To solve the problem of finding the maximum distance to the closest person when choosing a seat, we follow these steps:

1. Pass from left to right: For each seat, track the distance to the last seen occupied seat on the left. If there’s no person to the left, set the distance to infinity.

2. Pass from right to left: Repeat the process but now track the distance to the closest person on the right. Again, if no person is found to the right, treat the distance as infinity.

3. Compute the minimum of both distances for each empty seat: This gives the shortest distance to the nearest person from both directions.

4. Track the maximum of these minimum distances: This represents the best possible seat Alex can choose to maximize his distance from the nearest person.

This two-pass strategy ensures an efficient O(n) solution and covers edge cases such as when Alex must sit at either end of the row.

Solutions

class Solution {
    public int findMaxDistance(int[] places) {
        int length = places.length;
        int emptyCount = 0; // current maximum gap of zeros
        int maximumDistance = 0;

        for (int index = 0; index < length; ++index) {
            if (places[index] == 1) {
                emptyCount = 0;
            } else {
                emptyCount++;
                maximumDistance = Math.max(maximumDistance, (emptyCount + 1) / 2);
            }
        }

        for (int index = 0; index < length; ++index) {
            if (places[index] == 1) {
                maximumDistance = Math.max(maximumDistance, index);
                break;
            }
        }

        for (int index = length - 1; index >= 0; --index) {
            if (places[index] == 1) {
                maximumDistance = Math.max(maximumDistance, length - 1 - index);
                break;
            }
        }

        return maximumDistance;
    }
}