Problem Description

You are given an array seats where each element is either 1 (a seat is occupied) or 0 (a seat is empty). The seats are arranged in a single row.
Your task is to find the maximum distance to the closest person that you can achieve by choosing one empty seat to sit in. You must sit in an empty seat (where seats[i] == 0), and you want to maximize the minimum distance to the nearest occupied seat.

Constraints:

• There is at least one empty seat and at least one occupied seat.
• There is always a valid solution.
• You cannot reuse or move people already sitting.
• Return the largest possible distance to the closest person you can get by choosing one seat.

Thought Process

At first glance, the problem may seem to require checking every empty seat and, for each, scanning left and right to find the nearest occupied seat. This brute-force approach would work, but it is inefficient, especially for long rows.

To optimize, we realize that the distance to the closest person for any empty seat depends on the nearest occupied seats to its left and right. If we precompute these distances, we can avoid redundant scans.

The problem is similar to finding the largest gap between occupied seats, but with special consideration for empty stretches at the ends. We should also consider the cases where the row starts or ends with empty seats, as the "distance" at the ends is simply the length of the empty stretch.

Solution Approach

Let's break down the optimized approach step by step:

1. Scan from Left to Right:
   • For each seat, keep track of the distance to the closest occupied seat on the left.
   • Initialize a variable (e.g., prev) to store the index of the last seen occupied seat.
2. Scan from Right to Left:
   • Similarly, for each seat, keep track of the distance to the closest occupied seat on the right.
   • Initialize a variable (e.g., next) to store the index of the next occupied seat to the right.
3. Combine the Results:
   • For each empty seat, the distance to the closest person is the minimum of the left and right distances.
   • Keep track of the maximum of these minimum distances.
4. Special Cases:
   • If an empty seat is at the start or end of the row, its distance is just the stretch to the nearest occupied seat.

Example Walkthrough

Let's use the sample input seats = [1,0,0,0,1,0,1]:

• First, scan from left to right:
  • At index 0: occupied (distance = 0)
  • At index 1: previous occupied at 0 (distance = 1)
  • At index 2: previous occupied at 0 (distance = 2)
  • At index 3: previous occupied at 0 (distance = 3)
  • At index 4: occupied (distance = 0)
  • At index 5: previous occupied at 4 (distance = 1)
  • At index 6: occupied (distance = 0)
• Now scan from right to left:
  • At index 6: occupied (distance = 0)
  • At index 5: next occupied at 6 (distance = 1)
  • At index 4: occupied (distance = 0)
  • At index 3: next occupied at 4 (distance = 1)
  • At index 2: next occupied at 4 (distance = 2)
  • At index 1: next occupied at 4 (distance = 3)
  • At index 0: occupied (distance = 0)
• For each empty seat, take the minimum of the left and right distances:
  • Index 1: min(1,3) = 1
  • Index 2: min(2,2) = 2
  • Index 3: min(3,1) = 1
  • Index 5: min(1,1) = 1
• The maximum among these is 2, which is the answer.

Time and Space Complexity

Brute-force Approach:

• For each empty seat, scan left and right to find the closest occupied seat.
• Time Complexity: O(N²) where N is the number of seats.
• Space Complexity: O(1) (no extra storage needed).

• Two linear scans (left-to-right and right-to-left) to precompute distances.
• Final pass to compute the answer.
• Time Complexity: O(N), since each scan is linear.
• Space Complexity: O(N), for storing left and right distance arrays (can be O(1) with careful variable use).

Summary

This problem demonstrates the power of precomputing information to avoid redundant work. By scanning the row from both directions, we can quickly determine the closest person to each seat and efficiently find the optimal place to sit. The solution is elegant because it reduces a seemingly complex problem to a few simple linear passes, making it both fast and easy to understand.

Code Implementation

class Solution:
    def maxDistToClosest(self, seats):
        n = len(seats)
        left = [n] * n
        right = [n] * n

        # Fill left array
        prev = -n
        for i in range(n):
            if seats[i] == 1:
                prev = i
                left[i] = 0
            else:
                left[i] = i - prev

        # Fill right array
        next = 2 * n
        for i in range(n - 1, -1, -1):
            if seats[i] == 1:
                next = i
                right[i] = 0
            else:
                right[i] = next - i

        max_dist = 0
        for i in range(n):
            if seats[i] == 0:
                dist = min(left[i], right[i])
                max_dist = max(max_dist, dist)
        return max_dist
      

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int n = seats.size();
        vector<int> left(n, n), right(n, n);

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

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

        int max_dist = 0;
        for (int i = 0; i < n; ++i) {
            if (seats[i] == 0) {
                int dist = min(left[i], right[i]);
                max_dist = max(max_dist, dist);
            }
        }
        return max_dist;
    }
};
      

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

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

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

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

var maxDistToClosest = function(seats) {
    const n = seats.length;
    const left = new Array(n).fill(n);
    const right = new Array(n).fill(n);

    let prev = -n;
    for (let i = 0; i < n; i++) {
        if (seats[i] === 1) {
            prev = i;
            left[i] = 0;
        } else {
            left[i] = i - prev;
        }
    }

    let next = 2 * n;
    for (let i = n - 1; i >= 0; i--) {
        if (seats[i] === 1) {
            next = i;
            right[i] = 0;
        } else {
            right[i] = next - i;
        }
    }

    let maxDist = 0;
    for (let i = 0; i < n; i++) {
        if (seats[i] === 0) {
            let dist = Math.min(left[i], right[i]);
            maxDist = Math.max(maxDist, dist);
        }
    }
    return maxDist;
};