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.

Edge Cases & Clarifying Questions

• Are there any cases where all seats are empty or all are full? No, the constraints guarantee at least one empty and one occupied seat.
• What if the optimal seat is at the very beginning or the very end? Leading and trailing zeros are treated differently from zeros between two occupied seats, because they are only bounded by one person.
• Is the array extremely large? The length can be up to 20,000, so an O(N) solution is required to pass within typical time limits.

---

2. Interactive Analysis

Click a solution to visualize.

---

3. Intuition (The “Genesis”)

Brute Force Approach

A naive brute-force approach would be to iterate through every empty seat. For each empty seat i, scan to the left and to the right to find the nearest occupied seat. The distance to the closest person for seat i would be the minimum of these two distances. We then return the maximum of these distances across all empty seats. Since we scan up to N elements for each of the N empty seats, this approach takes O(N²) time, which is too slow for N = 20,000.

Optimized Approach

To optimize, we realize that we don’t need to rescan the entire array from scratch. Instead, we can observe the sizes of continuous blocks of empty seats (“gaps” of zeros). If we sit in an empty seat i, the distance to the closest person is min(distance to left person, distance to right person). We want to maximize this value globally.

Key Observation: In a block of K continuous zeros bounded by people on both sides (e.g., 1, 0, 0, 0, 1), the best seat is right in the middle. The distance from this middle seat to either person is (K + 1) / 2. We also must consider two special bounding cases where zeros are not bounded on both sides:

1. Leading Zeros: 0, 0, 0, 1... → The distance is exactly K (the distance to the first person).
2. Trailing Zeros: ...1, 0, 0 → The distance is exactly K (the distance to the last person).

Pattern Name: Group By Zero / Two Pointers

Common Pitfalls

• Incorrectly dividing edge blocks: A common mistake is dividing the length of leading or trailing zero blocks by 2. Unlike internal blocks, these edge gaps are only bounded by one person, meaning we can sit at the extreme end to maximize distance.
• Handling odd vs. even gaps: Using integer division (K + 1) / 2 correctly calculates the optimal distance for both even and odd length gaps without requiring separate logic.

---

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.