# Maximize Distance to Closest Person
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-distance-to-closest-person)
Canonical: https://scaleengineer.com/dsa/problems/maximize-distance-to-closest-person
**Data structures:** Array
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Samsung](https://scaleengineer.com/companies/samsung), [Snowflake](https://scaleengineer.com/companies/snowflake), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Snap](https://scaleengineer.com/companies/snap), [VK](https://scaleengineer.com/companies/vk)
---
## Problem
You are given an array representing a row of `seats` where `seats[i] = 1` represents a person sitting in the `ith` seat, and `seats[i] = 0` represents that the `ith` 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_.

**Example 1:**

![](https://assets.glich.co/dsa/maximize-distance-to-closest-person/image0.jpg) 

**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

**Constraints:**

* `2 <= seats.length <= 2 * 104`
* `seats[i]` is `0` or `1`.
* At least one seat is **empty**.
* At least one seat is **occupied**.

# Approaches
## Brute Force Iteration
This approach involves iterating through every empty seat and, for each one, calculating the distance to the nearest person on the left and the nearest person on the right. The minimum of these two distances is the "distance to the closest person" for that specific empty seat. We keep track of the maximum such distance found across all empty seats.
**Time:** O(N^2), where N is the number of seats. For each of the O(N) empty seats, we might scan the entire array in the worst case to find the nearest left and right person. · **Space:** O(1), as we only use a few variables to store distances and indices.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient for large inputs due to the O(N^2) time complexity.
### Explanation
We can solve this problem by checking every possible empty seat. For each empty seat, we need to determine the distance to the closest person. This involves two sub-problems: finding the closest person to the left and finding the closest person to the right. We can do this by scanning leftwards and rightwards from the current empty seat. The smaller of these two distances is the score for that seat. We then iterate through all empty seats, calculate their scores, and return the maximum score found.

```java
class Solution {
    public int maxDistToClosest(int[] seats) {
        int n = seats.length;
        int maxDistance = 0;
        for (int i = 0; i < n; i++) {
            if (seats[i] == 0) {
                // Find closest person to the left
                int leftDist = n; // Initialize with a large value
                for (int j = i - 1; j >= 0; j--) {
                    if (seats[j] == 1) {
                        leftDist = i - j;
                        break;
                    }
                }
                
                // Find closest person to the right
                int rightDist = n; // Initialize with a large value
                for (int j = i + 1; j < n; j++) {
                    if (seats[j] == 1) {
                        rightDist = j - i;
                        break;
                    }
                }
                
                int currentMinDist = Math.min(leftDist, rightDist);
                maxDistance = Math.max(maxDistance, currentMinDist);
            }
        }
        return maxDistance;
    }
}
```
### Algorithm
- Initialize `maxDistance` to 0.
- Iterate through the `seats` array with an index `i` from 0 to `n-1`.
- If `seats[i]` is 0 (an empty seat):
  - Find the distance to the nearest person on the left, `leftDist`. Search backwards from `i-1` to 0. If no person is found, `leftDist` is effectively infinite.
  - Find the distance to the nearest person on the right, `rightDist`. Search forwards from `i+1` to `n-1`. If no person is found, `rightDist` is effectively infinite.
  - The distance for the current empty seat `i` is `min(leftDist, rightDist)`.
  - Update `maxDistance = max(maxDistance, min(leftDist, rightDist))`.
- After checking all seats, return `maxDistance`.

## Two-Pass using Auxiliary Arrays
This approach improves upon the brute-force method by pre-calculating the distances to the nearest person on the left and right for every seat. We use two auxiliary arrays for this purpose, which allows us to find the answer in a linear number of passes.
**Time:** O(N). We perform three separate passes over the array (one for `left`, one for `right`, and one for the final calculation), each taking O(N) time. This simplifies to O(N). · **Space:** O(N), as we use two auxiliary arrays, `left` and `right`, each of size N.
**Pros:** Much faster than the brute-force approach with a linear time complexity.; The logic is still relatively straightforward, breaking the problem down into smaller, manageable passes.
**Cons:** Requires extra space proportional to the input size, which might be a concern for very large inputs.
### Explanation
Instead of repeatedly scanning for the nearest person for each empty seat, we can precompute this information. We use two passes and two auxiliary arrays, `left` and `right`.

1.  **Left Pass**: We create an array `left` where `left[i]` stores the distance from seat `i` to the nearest person on its left. We populate this by iterating from left to right. If `seats[i]` has a person, `left[i]` is 0. Otherwise, `left[i]` is `left[i-1] + 1`.
2.  **Right Pass**: Similarly, we create an array `right` where `right[i]` stores the distance to the nearest person on its right. We populate this by iterating from right to left.
3.  **Final Pass**: With `left` and `right` arrays computed, we iterate through the seats one last time. For each empty seat `i`, the distance to the closest person is simply `min(left[i], right[i])`. We find the maximum of these minimums over all empty seats.

```java
class Solution {
    public int maxDistToClosest(int[] seats) {
        int n = seats.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        // Fill left array
        int dist = n; // Represents infinity
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                dist = 0;
            } else {
                dist++;
            }
            left[i] = dist;
        }
        
        // Fill right array
        dist = n; // Represents infinity
        for (int i = n - 1; i >= 0; i--) {
            if (seats[i] == 1) {
                dist = 0;
            } else {
                dist++;
            }
            right[i] = dist;
        }
        
        // Find the maximum of the minimums
        int maxDistance = 0;
        for (int i = 0; i < n; i++) {
            if (seats[i] == 0) {
                maxDistance = Math.max(maxDistance, Math.min(left[i], right[i]));
            }
        }
        
        return maxDistance;
    }
}
```
### Algorithm
- Create an integer array `left` of size `n`.
- Initialize a distance variable `dist` to a large value (e.g., `n`).
- Iterate from `i = 0` to `n-1`:
  - If `seats[i] == 1`, reset `dist = 0`.
  - Else, increment `dist`.
  - Set `left[i] = dist`.
- Create an integer array `right` of size `n`.
- Reset `dist` to a large value.
- Iterate from `i = n-1` down to `0`:
  - If `seats[i] == 1`, reset `dist = 0`.
  - Else, increment `dist`.
  - Set `right[i] = dist`.
- Initialize `max_dist = 0`.
- Iterate from `i = 0` to `n-1`:
  - If `seats[i] == 0`, calculate `current_dist = min(left[i], right[i])`.
  - Update `max_dist = max(max_dist, current_dist)`.
- Return `max_dist`.

## One-Pass Solution
The most efficient approach solves the problem in a single pass with constant extra space. The key insight is that the maximum distance can only occur in one of three scenarios: an empty block of seats at the beginning, an empty block at the end, or an empty block between two people. We can calculate the maximum distance for each of these cases as we iterate through the array.
**Time:** O(N), as we iterate through the array only once. · **Space:** O(1), as we only use a few variables to keep track of the last person's index and the maximum distance.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).
**Cons:** The logic can be slightly more complex to reason about initially, as it combines multiple cases (leading, middle, and trailing gaps) into a single pass.
### Explanation
We can optimize to a single pass by realizing that the problem is about finding the largest gap of empty seats. We can iterate through the seats, keeping track of the index of the last person we've seen (`lastPersonIndex`).

- **Gaps between people**: When we are at index `i` and find a person (`seats[i] == 1`), and we have seen a person before at `lastPersonIndex`, the number of empty seats between them is `i - lastPersonIndex - 1`. The best place to sit in this gap is in the middle, which gives a maximum distance of `(i - lastPersonIndex) / 2` to the nearest person. We update our global maximum distance with this value.

- **Leading empty seats**: If we find the first person at index `i`, it means seats `0` to `i-1` were empty. The best place to sit is at index `0`, giving a distance of `i`. This is a special case we handle when we find the very first person.

- **Trailing empty seats**: After the loop finishes, we need to account for any empty seats at the end of the row. The distance from the last person at `lastPersonIndex` to the end of the row (`n-1`) is `n - 1 - lastPersonIndex`. This is another potential maximum.

By tracking `lastPersonIndex` and updating the max distance as we find each person, we can solve the problem in one pass.

```java
class Solution {
    public int maxDistToClosest(int[] seats) {
        int n = seats.length;
        int maxDistance = 0;
        int lastPersonIndex = -1;

        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (lastPersonIndex == -1) {
                    // Case: leading zeros. Alex sits at index 0.
                    maxDistance = i;
                } else {
                    // Case: zeros between two people. Alex sits in the middle.
                    maxDistance = Math.max(maxDistance, (i - lastPersonIndex) / 2);
                }
                lastPersonIndex = i;
            }
        }

        // Case: trailing zeros. Alex sits at the last seat.
        if (lastPersonIndex != n - 1) {
            maxDistance = Math.max(maxDistance, n - 1 - lastPersonIndex);
        }

        return maxDistance;
    }
}
```
### Algorithm
- Initialize `max_dist = 0` and `last_person_index = -1`.
- Loop through each seat `i` from `0` to `n-1`.
- If `seats[i] == 1`:
  - If `last_person_index == -1` (this is the first person found), the maximum distance is `i` (for sitting at `seats[0]`).
  - Else, there is a gap of empty seats between `last_person_index` and `i`. The best place to sit is in the middle, at a distance of `(i - last_person_index) / 2` from either person. Update `max_dist` with this value if it's larger.
  - Update `last_person_index = i`.
- After the loop, handle the case of trailing empty seats. The distance from the end of the row to the last person is `n - 1 - last_person_index`. Update `max_dist` with this value if it's larger.
- Return `max_dist`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int: first = last = None d = 0 for i, c in enumerate(seats): if c: if last is not None: d = max(d, i - last) if first is None: first = i last = i return max(first, len(seats) - last - 1, d // 2)

```