Problem Description

You have an array seats representing a row of seats where:

• seats[i] = 1 means a person is sitting in the i-th seat
• seats[i] = 0 means the i-th seat is empty
• The array is 0-indexed

The problem guarantees that there is at least one empty seat and at least one person sitting.

Alex wants to find an empty seat to sit in such that he maximizes the distance to the closest person next to him. Your task is to return this maximum possible distance.

For example, if seats = [1, 0, 0, 0, 1, 0, 1], Alex could sit at index 2, which gives him a distance of 2 from the closest person. This would be the maximum possible distance he could achieve in this arrangement.

The distance is measured as the number of seats between Alex and the nearest person. You need to consider:

• Empty seats at the beginning (distance from the first person)
• Empty seats at the end (distance from the last person)
• Empty seats between two people (distance to the closer person)

Intuition

To maximize Alex's distance from the closest person, we need to consider three possible scenarios for where Alex could sit:

1. At the beginning of the row: If there are empty seats before the first person, Alex could sit at seat 0. The distance would be equal to the position of the first person.

2. At the end of the row: If there are empty seats after the last person, Alex could sit at the last seat. The distance would be n - last_person_position - 1.

3. Between two people: If there's a gap between two people, Alex should sit in the middle of that gap to maximize distance from both. If the gap has length d, sitting in the middle gives a distance of d // 2 to the closest person.

The key insight is that we only need to track:

• The position of the first person (first)
• The position of the last person (last)
• The maximum gap between any two consecutive people (d)

As we traverse the array once, whenever we encounter a person:

• If it's the first person we've seen, we record their position
• If we've seen people before, we calculate the gap from the previous person
• We always update the position of the most recent person we've seen

After the traversal, we have all the information needed to determine the maximum distance: it's the maximum of sitting at the beginning, sitting at the end, or sitting in the middle of the largest gap between two people.

Solution Approach

We implement a single-pass traversal algorithm to find the maximum distance to the closest person.

Variables Used:

• first: Tracks the position of the first person in the array (initially None)
• last: Tracks the position of the most recently seen person (initially None)
• d: Tracks the maximum distance between any two consecutive people (initially 0)

Algorithm Steps:

1. Traverse the array using enumeration to get both index i and value c:

   for i, c in enumerate(seats):

2. When we encounter a person (c == 1):

   • Update maximum gap: If last is not None (meaning we've seen a person before), calculate the gap between current person and previous person: d = max(d, i - last)
   • Record first person: If first is None (meaning this is the first person), set first = i
   • Update last person: Always update last = i to track the most recent person's position

3. Calculate the final result by taking the maximum of three values:

   • first: Distance if Alex sits at seat 0 (beginning)
   • len(seats) - last - 1: Distance if Alex sits at the last seat (end)
   • d // 2: Distance if Alex sits in the middle of the largest gap between two people

The reason we use d // 2 for gaps between people is that Alex would sit in the middle of the gap to maximize distance from both neighbors. For example, if there's a gap of 4 empty seats between two people, sitting in the middle gives a distance of 2 to the closest person.

Time Complexity: O(n) where n is the length of the seats array (single pass)
Space Complexity: O(1) as we only use a constant amount of extra space

Example Walkthrough

Let's walk through the solution with seats = [1, 0, 0, 0, 1, 0, 1]:

Initial State:

• first = None (haven't seen first person yet)
• last = None (haven't seen any person yet)
• d = 0 (no gaps calculated yet)

Traversal:

1. i = 0, c = 1 (person at seat 0)

   • Since last = None, we don't calculate any gap
   • Since first = None, set first = 0
   • Update last = 0
   • State: first = 0, last = 0, d = 0

2. i = 1, c = 0 (empty seat)

   • Skip (only process when we find a person)

3. i = 2, c = 0 (empty seat)

   • Skip

4. i = 3, c = 0 (empty seat)

   • Skip

5. i = 4, c = 1 (person at seat 4)

   • Since last = 0, calculate gap: d = max(0, 4 - 0) = 4
   • first remains 0
   • Update last = 4
   • State: first = 0, last = 4, d = 4

6. i = 5, c = 0 (empty seat)

   • Skip

7. i = 6, c = 1 (person at seat 6)

   • Since last = 4, calculate gap: d = max(4, 6 - 4) = max(4, 2) = 4
   • first remains 0
   • Update last = 6
   • State: first = 0, last = 6, d = 4

Final Calculation:

• Distance if sitting at beginning: first = 0 (no empty seats before first person)
• Distance if sitting at end: 7 - 6 - 1 = 0 (no empty seats after last person)
• Distance if sitting between people: d // 2 = 4 // 2 = 2

Result: max(0, 0, 2) = 2

Alex should sit at index 2 (middle of the gap between seats 0 and 4), giving him a distance of 2 from the closest person.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array seats. The algorithm iterates through the array exactly once using the enumerate function, performing constant-time operations (comparisons and assignments) for each element.

The space complexity is O(1). The algorithm only uses a fixed number of variables (first, last, d, i, and c) regardless of the input size, requiring constant extra space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Edge Cases (Beginning and End Seats)

Pitfall: A common mistake is only considering gaps between occupied seats and using max_distance // 2 as the final answer, forgetting that sitting at the very first or very last seat might provide a greater distance.

Example of Incorrect Approach:

def maxDistToClosest(self, seats: List[int]) -> int:
    max_gap = 0
    last_person = -1
  
    for i, seat in enumerate(seats):
        if seat == 1:
            if last_person != -1:
                max_gap = max(max_gap, i - last_person)
            last_person = i
  
    return max_gap // 2  # WRONG: Ignores edge seats!

Why it fails: For seats = [1, 0, 0, 0], this would return 0, but the correct answer is 3 (sitting at the last seat).

Solution: Always consider three cases:

• Distance from seat 0 to the first person
• Distance from the last seat to the last person
• Half the maximum gap between any two people

2. Integer Division Confusion for Odd Gaps

Pitfall: Not understanding why we use integer division (//) instead of regular division when calculating max_distance_between_occupied // 2.

Example: If the gap between two people is 5 seats (indices 1 and 7 are occupied, with empty seats at 2,3,4,5,6), Alex should sit at index 4, giving a distance of 2 to the nearest person. Using 5 // 2 = 2 is correct, but some might think we need ceil(5 / 2) = 3.

Why // is correct: When sitting between two people, we want the minimum distance to either neighbor. For a gap of size d:

• Odd gap (e.g., 5): Sitting in the middle gives distance 2 to both neighbors
• Even gap (e.g., 4): Sitting at either middle position gives distance 1 to one neighbor and 2 to the other

The floor division naturally gives us the correct minimum distance.

3. Off-by-One Error When Calculating Distance to End

Pitfall: Incorrectly calculating the distance when sitting at the last seat.

Incorrect: len(seats) - last_occupied
Correct: len(seats) - last_occupied - 1

Example: For seats = [1, 0, 0]:

• Last occupied is at index 0
• Last seat is at index 2
• Distance = 2 - 0 = 2 ❌ (This would be counting seats, not gaps)
• Distance = 2 - 0 - 1 = 1 ❌ (This is also wrong!)
• Actually: len(seats) - 1 - last_occupied = 3 - 1 - 0 = 2 ✅

Better way to think about it: The last index is len(seats) - 1, so the distance from last_occupied to the last seat is (len(seats) - 1) - last_occupied.