Maximize Distance to Closest Person

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

1. Problem Definition

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.

Return the maximum distance to the closest person.

Constraints:

• 2 ≤ seats.length ≤ 20,000
• At least one seat is empty.
• At least one seat is occupied.

---

2. Interactive Analysis

Click a solution to visualize.

---

3. Intuition

We can solve this by looking at “gaps” of zeros. If we sit in a seat i, the distance to the closest person is min(distance to left person, distance to right person). We want to maximize this value.

Key Observation: In a block of K continuous zeros surrounded by people (e.g., 1, 0, 0, 0, 1), the best seat is right in the middle. The distance is (K + 1) / 2. Edge cases:

1. Leading Zeros: 0, 0, 0, 1... -> Distance is just K (distance to the first person).
2. Trailing Zeros: ...1, 0, 0 -> Distance is just K (distance to the last person).

---

4. Solutions

Approach 1: Next Array (DP)

Pre-calculate distances to people on the left and right.

Java

Go

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; i < n; ++i) {
        if (seats[i] == 1) left[i] = 0;
        else if (i > 0) left[i] = left[i-1] + 1;
    }

    for (int i = n - 1; i >= 0; --i) {
        if (seats[i] == 1) right[i] = 0;
        else if (i < n - 1) right[i] = right[i+1] + 1;
    }

    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (seats[i] == 0)
            ans = Math.max(ans, Math.min(left[i], right[i]));
    return ans;
}

func maxDistToClosest(seats []int) int {
    n := len(seats)
    left := make([]int, n)
    right := make([]int, n)
    for i := range left { left[i], right[i] = n, n }

    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            left[i] = 0
        } else if i > 0 {
            left[i] = left[i-1] + 1
        }
    }

    for i := n - 1; i >= 0; i-- {
        if seats[i] == 1 {
            right[i] = 0
        } else if i < n - 1 {
            right[i] = right[i+1] + 1
        }
    }

    ans := 0
    for i := 0; i < n; i++ {
        if seats[i] == 0 {
            d := left[i]
            if right[i] < d { d = right[i] }
            if d > ans { ans = d }
        }
    }
    return ans
}

Approach 2: Group By Zero (Space Optimal)

The max distance is determined by the largest block of zeros.

Java

Go

public int maxDistToClosest(int[] seats) {
    int n = seats.length;
    int k = 0, ans = 0;

    for (int i = 0; i < n; ++i) {
        if (seats[i] == 1) k = 0;
        else {
            k++;
            ans = Math.max(ans, (k + 1) / 2);
        }
    }

    for (int i = 0; i < n; ++i) {
        if (seats[i] == 1) {
            ans = Math.max(ans, i);
            break;
        }
    }

    for (int i = n - 1; i >= 0; --i) {
        if (seats[i] == 1) {
            ans = Math.max(ans, n - 1 - i);
            break;
        }
    }

    return ans;
}

func maxDistToClosest(seats []int) int {
    n := len(seats)
    ans, k := 0, 0

    for _, s := range seats {
        if s == 1 {
            k = 0
        } else {
            k++
            if (k+1)/2 > ans { ans = (k + 1) / 2 }
        }
    }

    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            if i > ans { ans = i }
            break
        }
    }

    for i := n - 1; i >= 0; i-- {
        if seats[i] == 1 {
            if n-1-i > ans { ans = n - 1 - i }
            break
        }
    }

    return ans
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Next Array	O(N)	O(N)	Requires two auxiliary arrays.
Two Pointer	O(N)	O(1)	Scan and track neighbors dynamically.
Group By Zero	O(N)	O(1)	Most efficient for streaming data.