algoadvance

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the i-th seat, and seats[i] = 0 represents that the i-th 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 to the closest person is maximized. Return that maximum distance to the closest person.

Example:

Input:

seats = [1,0,0,0,1,0,1]

Output:

2

Input:

seats = [1,0,0,0]

Output:

3

Input:

seats = [0,1]

Output:

1

Clarifying Questions:

  1. Is the input always valid, meaning it always contains at least one 1 and at least one 0?
    • Yes.
  2. Can the row be of any length?
    • Yes, the row length is variable.

Strategy

To solve the problem, we need to consider three main cases:

  1. The longest stretch of empty seats between two seated people.
  2. The stretch of empty seats from the start of the array to the first seated person.
  3. The stretch of empty seats from the last seated person to the end of the array.

We can use a linear scan to determine these values. During the scan:

The main steps:

  1. Initialize variables to store the maximum distances.
  2. Traverse the list once and calculate the distances considering the aforementioned cases.
  3. Return the maximum of these calculated distances.

Code

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

Time Complexity

The code runs in O(n) time complexity as we are iterating through the list once to determine the distance. This ensures it’s efficient even for large inputs. The space complexity is O(1) because we are using a constant amount of extra space regardless of input size.

Try our interview co-pilot at AlgoAdvance.com