Maximize Distance to Closest Person

medium array two-pointers

Problem

seats[i] is 1 if occupied and 0 otherwise. Choose an empty seat to maximize the distance to the closest person. Return that maximum distance.

Inputseats = [1,0,0,0,1,0,1]

Output2

Sitting at index 2 gives distance 2 to both neighbors.

input

def maxDistToClosest(seats):
    n = len(seats)
    last = -1
    best = 0
    for i in range(n):
        if seats[i] == 1:
            best = i if last == -1 else max(best, (i - last) // 2)
            last = i
    best = max(best, n - 1 - last)
    return best

function maxDistToClosest(seats) {
  const n = seats.length;
  let last = -1, best = 0;
  for (let i = 0; i < n; i++) {
    if (seats[i] === 1) {
      best = last === -1 ? i : Math.max(best, Math.floor((i - last) / 2));
      last = i;
    }
  }
  best = Math.max(best, n - 1 - last);
  return best;
}

class Solution {
  public int maxDistToClosest(int[] seats) {
    int n = seats.length, last = -1, best = 0;
    for (int i = 0; i < n; i++) {
      if (seats[i] == 1) {
        best = (last == -1) ? i : Math.max(best, (i - last) / 2);
        last = i;
      }
    }
    best = Math.max(best, n - 1 - last);
    return best;
  }
}

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int n = seats.size(), last = -1, best = 0;
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                best = (last == -1) ? i : max(best, (i - last) / 2);
                last = i;
            }
        }
        best = max(best, n - 1 - last);
        return best;
    }
};

Explanation

The best empty seat is the one farthest from any person, so we only care about the gaps of empty seats between occupied ones. We sweep once, remembering the last person we saw.

We track last (index of the previous occupied seat) and best (best distance found). Each time we hit a person at index i:

If it is the first person (last == -1), the leading empty seats let you sit at the very start, giving distance i. Otherwise, sitting in the middle of the gap between two people gives (i - last) / 2.

After the loop we also check the trailing empties with n - 1 - last, since you can sit at the far end past the last person. The biggest of all these is the answer.

Example: [1,0,0,0,1,0,1]. The gap between seats 0 and 4 gives 4/2 = 2, which beats the others, so the max distance is 2.

Time: O(n) Space: O(1)