3.27 Maximize Distance to Closest Person

3.27.1 Problem Metadata

3.27.2 Description

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.

3.27.3 Examples

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

3.27.4 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

3.27.5 Solution - One-Pass Greedy

3.27.5.1 Walkthrough

The key insight is that Alex can sit in three possible locations to maximize distance:

  1. At the beginning (before the first person): Distance = index of first person
  2. In the middle (between two people): Distance = (gap between them) / 2
  3. At the end (after the last person): Distance = (n - 1) - index of last person

We track the maximum distance across all three scenarios by scanning through the array once:

  • First, find the first person and record the distance from the start.
  • Then, continue scanning to find subsequent people, calculating the half-distance between consecutive occupied seats.
  • Finally, calculate the distance from the last person to the end of the array.

The maximum of these three distances is the answer.

3.27.5.2 Analysis

  • Time Complexity: O(n) - Single pass through the array. The first loop finds the first person, then the second loop continues from there to the end. Each element is visited exactly once.
  • Space Complexity: O(1) - Only uses a constant amount of extra space for tracking indices and distances.

3.27.5.3 Implementation Steps

  1. Initialize max = 0 to track the maximum distance, and index to track the position of the last person seen.
  2. Find the first person:
    • Iterate from the start until finding the first seats[i] == 1.
    • Set max = i (distance from start to first person).
    • Set index = i and break.
  3. Find distances between people:
    • Continue iterating from index to the end.
    • When finding another person at position i:
      • Calculate dist = (i - index) / 2 (Alex sits in the middle of the gap).
      • Update max = Math.max(max, dist).
      • Update index = i (track the new last person position).
  4. Calculate distance to the end:
    • Compute dist = (n - 1) - index (distance from last person to end).
    • Update max = Math.max(max, dist).
  5. Return max.

3.27.5.4 Code - Java

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

        int dist = 0;
        int max = 0; // max distance
        int index = 0; // 

        // locate the first person
        for(int i = 0; i < n; i++) {
            if(seats[i] == 1) {
                dist = i;
                max = dist; //distance = i - 0
                index = i;                
                break;
            }
        }

        // Locate the next seat sitting in between two people
        for(int i = index; i < n; i++) {
            if(seats[i] == 1) {
                dist = (i - index) / 2;
                max = Math.max(max, dist);  // distance = (i - begin_index ) / 2
                index = i;
            }
        }

        // locate the distance of last seat vs last person
        dist = (n - 1) - index;
        max = Math.max(max, dist);

        return max;
    }
}