Maximize Distance to Closest Person

[!NOTE] This module explores the core principles of the “Maximize Distance to Closest Person” problem, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Problem Statement

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. You want to sit in a seat such that the distance between you and the closest person is maximized.

Return that maximum distance.

2. Interactive Comparison

Visualize how different strategies navigate the seating arrangement.

Select a strategy to begin.

3. The 3 Strategies

Strategy A: Next Array (Pre-computation)

Create two arrays: leftDist[i] and rightDist[i], storing the distance to the closest person to the left and right, respectively. The answer for index i is min(leftDist[i], rightDist[i]).

Time: O(N)
Space: O(N)

Strategy B: Two Pointer

For each empty seat, find the index of the nearest person to the left and right.

Time: O(N) (if implemented by tracking the previous person as you iterate).
Space: O(1)

Strategy C: Group By Zero

Max distance occurs in one of three places:

Beginning: Consecutive zeros at the start.
Ending: Consecutive zeros at the end.
Middle: A block of K zeros between two people has a max distance of (K+1)/2.

Time: O(N)
Space: O(1)

4. Implementation (Java)

Group By Zero Approach (Optimal Space)

class Solution {
    public int maxDistToClosest(int[] seats) {
        int n = seats.length;
        int ans = 0;
        int i = 0;
        int curr = 0;

        // Middle and General Pass
        while(i < n) {
            if(seats[i] == 1) {
                curr = 0;
            } else {
                curr++;
                ans = Math.max(ans, (curr + 1) / 2);
            }
            i++;
        }

        // Boundary: Start
        i = 0;
        while(i < n && seats[i] == 0) {
            ans = Math.max(ans, i + 1);
            i++;
        }

        // Boundary: End
        i = n - 1;
        while(i >= 0 && seats[i] == 0) {
            ans = Math.max(ans, n - i - 1);
            i--;
        }

        return ans;
    }
}

5. Summary Table

Approach	Time	Space	Pros	Cons
Next Array	`O(N)`	`O(N)`	Simple logic	Extra space
Two Pointer	`O(N)`	`O(1)`	No extra space	More boundary checks
Group By Zero	`O(N)`	`O(1)`	Most efficient	Slightly abstract