Maximize Distance to Closest Person

Medium

Google

1 view

Topics:

ArraysTwo Pointers

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:

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.

Maximize Distance to Closest Person

Medium

Google

1 view

Topics:

ArraysTwo Pointers

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:

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the `seats` array?
Is it guaranteed that there is at least one empty seat (represented by 0) in the `seats` array?
Is it guaranteed that there is at least one occupied seat (represented by 1) in the `seats` array?
If all seats are occupied or all seats are empty, what should I return?
Can I assume the input array `seats` only contains 0s and 1s?

Brute Force Solution

Approach

The problem asks us to find the best seat in a row such that it maximizes the distance to the nearest occupied seat. The brute force way is all about trying every single empty seat and figuring out how good it is.

Here's how the algorithm would work step-by-step:

Go through each empty seat one by one.
For each empty seat, find the distance to the closest person sitting to its left and the closest person sitting to its right.
Take the smaller of those two distances; this tells you how 'far away' that seat is from people.
Remember the biggest 'far away' distance you find while checking all the empty seats.
After checking all the empty seats, the biggest 'far away' distance you remembered is your answer, and the seat that gave you that distance is the best seat.

Code Implementation

def max_distance_to_closest(seats):
    max_distance = 0
    
    for i in range(len(seats)):
        if seats[i] == 0:
            # Only consider empty seats

            left_distance = float('inf')
            right_distance = float('inf')

            for j in range(i - 1, -1, -1):
                if seats[j] == 1:
                    left_distance = i - j
                    break
            
            for j in range(i + 1, len(seats)):
                if seats[j] == 1:
                    right_distance = j - i
                    break
            
            closest_distance = min(left_distance, right_distance)

            # Keeps track of maximum distance found
            max_distance = max(max_distance, closest_distance)
            
    return max_distance

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n seats. For each empty seat, it finds the closest person to the left and right. Finding the closest person requires, in the worst case, iterating through all other seats. Thus, for each of the n seats, we potentially perform another O(n) operation to find the minimum distance. This results in a nested loop behavior, approximating n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The brute-force approach, as described, iterates through the input array but doesn't use any auxiliary data structures proportional to the input size. It maintains variables to track distances to the closest person, but these variables occupy constant space regardless of the size of the input array (denoted as N, representing the number of seats). The algorithm's space usage remains constant irrespective of N. Thus, the space complexity is O(1).

Optimal Solution

Approach

The best way to solve this seating problem is to find the biggest gaps of empty seats. Then, place someone in the middle of the largest gap to maximize the distance to the nearest person. We'll handle the special cases of empty seats at the very beginning and end separately.

Here's how the algorithm would work step-by-step:

First, find all the consecutive stretches of empty seats.
Keep track of the length of each of those empty stretches.
Find the longest stretch of empty seats.
Place a person in the middle of this longest stretch. If the length of the stretch is even, pick the seat slightly towards the left.
Now, consider the empty seats at the very beginning and the very end separately.
If there are empty seats at the beginning, place a person at the very first seat.
If there are empty seats at the end, place a person at the very last seat.
Finally, compare the distances from the newly seated persons to their nearest neighbors and determine the maximum distance.

Code Implementation

def max_dist_to_closest(seats):
    max_distance = 0
    empty_seats = []
    current_empty_length = 0

    for seat_available in seats:
        if seat_available == 0:
            current_empty_length += 1
        else:
            if current_empty_length > 0:
                empty_seats.append(current_empty_length)
                current_empty_length = 0

    if current_empty_length > 0:
        empty_seats.append(current_empty_length)

    longest_stretch = 0
    longest_stretch_index = -1

    for index, length in enumerate(empty_seats):
        if length > longest_stretch:
            longest_stretch = length
            longest_stretch_index = index

    # Place a person in the middle of the longest stretch.
    if longest_stretch_index != -1:
        start_index = 0
        for i in range(longest_stretch_index):
            start_index += empty_seats[i] + 1
        
        seats[start_index + longest_stretch // 2] = 1

    # Handle empty seats at the beginning.
    if seats[0] == 0:
        seats[0] = 1

    # Handle empty seats at the end.
    if seats[-1] == 0:
        seats[-1] = 1

    last_person = -1
    for i in range(len(seats)):
        if seats[i] == 1:
            if last_person == -1:
                max_distance = i
            else:
                max_distance = max(max_distance, (i - last_person) // 2)
            last_person = i

    # Distance to the end if the last person is not at the end.
    max_distance = max(max_distance, len(seats) - 1 - last_person)

    return max_distance

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of seats to identify consecutive stretches of empty seats. Finding the longest stretch involves a single pass through the array (O(n)). Placing people at the beginning and end, and calculating the maximum distance also takes O(n) time. Therefore, the overall time complexity is dominated by the linear traversal of the array, resulting in O(n).

Space Complexity

O(N) – The algorithm needs to keep track of the length of each consecutive stretch of empty seats. This implies storing these lengths in a list or similar data structure. In the worst-case scenario, the entire array consists of alternating filled and empty seats, leading to storing potentially N/2 lengths which scales linearly with the input size N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty since no seats exist.
Array with only one seat	If the array has only one seat, return 1 if it's empty (0), and 0 if it's occupied (1).
All seats are occupied (all 1s)	Return 0 since no empty seat is available to maximize distance.
All seats are empty (all 0s)	Return the length of the array since the person can sit at either end and maximize the distance.
An empty seat is at the beginning of the row	The distance to the closest person is simply the index of the first occupied seat.
An empty seat is at the end of the row	The distance to the closest person is the length of the array minus one minus the index of the last occupied seat.
Consecutive empty seats in the middle of the row	The distance to the closest person is half the number of consecutive empty seats (rounded up) or the distances to left/right, depending on your implementation.
Integer overflow when calculating the distance if array size is close to maximum integer value	Use long data type to avoid potential integer overflow when calculating distances.