---

1. Problem Summary

You are given an array seats where:

• seats[i] = 1 means the seat is occupied
• seats[i] = 0 means the seat is empty

You must choose an empty seat such that the distance to the closest occupied seat is maximized, and return that maximum distance.

Important characteristics:

• You can only sit in seats with value 0
• Distance is measured by index difference
• There is guaranteed to be at least one empty seat
• There is guaranteed to be at least one occupied seat

Example interpretation:
If seats = [1,0,0,0,1,0,1], the best position is index 2 or 1 or 3, giving a max distance of 2.

---

2. Key Insights

Three cases determine distances

1. Empty stretch at the beginning
   Example: [0,0,0,1,...]
   Best distance = length of leading zeros
2. Empty stretch at the end
   Example: [...,1,0,0,0]
   Best distance = length of trailing zeros
3. Empty stretch between two occupied seats
   Example: 1,0,0,0,1
   Best distance = floor(length of gap / 2)

We only need to scan once

Track positions of occupied seats and compute distances.

Maximum among all gap-based distances is answer

Simply take the maximum of:

• leading gap
• trailing gap
• half of middle gaps

---

3. Approach

Linear scan with gap tracking

Steps:

1. Track index of previous occupied seat (prev = -1)
2. Initialize maxDistance = 0
3. Loop through array:
   • If seat is occupied:
     • If prev == -1:
       leading gap = index
       update maxDistance
     • Else:
       middle gap = (index – prev) / 2
       update maxDistance
     • update prev = index
4. After loop, account for trailing gap:
   trailing gap = (n – 1) – prev
   update maxDistance

Return maxDistance.

---

4. Time and Space Complexity

Time Complexity: O(N)

Single scan through seats.

Space Complexity: O(1)

Only a few tracking variables used.

---

5. Java Solution

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

        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (prev == -1) {
                    maxDistance = i;  // leading gap
                } else {
                    maxDistance = Math.max(maxDistance, (i - prev) / 2);
                }
                prev = i;
            }
        }

        // trailing gap
        maxDistance = Math.max(maxDistance, n - 1 - prev);

        return maxDistance;
    }
}

---

6. Dry Run Examples

Example 1

Input:

[1,0,0,0,1,0,1]

Occupied indexes at: 0, 4, 6

Leading gap:
0 → ignored (starts with 1)

Middle gap between 0 and 4:
(4 – 0) / 2 = 2 → max = 2

Middle gap between 4 and 6:
(6 – 4) / 2 = 1 → max remains 2

Trailing gap:
6 to end (index 6) → 6 to 6 = 0

Final answer:

2

---

Example 2

Input:

[1,0,0,0]

Leading gap: none
Middle gap: none
Trailing gap: 3 – 0 = 3

Answer:

3

---

Example 3

Input:

[0,0,0,1]

Leading gap:
index 3 → maxDistance = 3

Middle gap: none
Trailing gap: none

Answer:

3

---

Example 4

Input:

[0,1]

Leading gap = 1
Trailing gap = 0

Output:

1

---

Example 5

Input:

[1,0,1]

Middle gap:
(2 – 0) / 2 = 1

Output:

1

---

7. Why This Solution Works

• Correctly handles leading, middle, and trailing segments
• Uses simple arithmetic to compute distances
• Does not require storing all occupied positions
• One scan ensures efficiency
• Works for all seat configurations

---

8. Common Mistakes

1. Forgetting that middle gaps are halved
2. Forgetting to check trailing gap
3. Using two-pointer sliding window unnecessarily
4. Trying to compute distances from every zero (too slow)
5. Mishandling edge case when first seats are empty