Maximize Distance to Closest Person
Medium
0 views
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 * 104seats[i]is0or1.- 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 there a practical limit I should be aware of?
- Is it guaranteed that there will always be at least one '1' (occupied seat) and one '0' (empty seat) in the `seats` array?
- If there are multiple empty seats that yield the same maximum distance, is it acceptable to return any one of them, or is a specific seat preferred (e.g., the leftmost one)?
- Can I assume the input array `seats` only contains 0s and 1s, or are other integer values possible?
- Could the `seats` array be null or empty? If so, what should I return in that case?
Brute Force Solution
Approach
The problem is like arranging people on a bench to maximize the distance to the nearest person. The brute force way to solve this involves trying every possible seat for the new person. We'll check the distance to others for each possibility and select the best one.
Here's how the algorithm would work step-by-step:
- First, consider each empty seat on the bench, one at a time.
- For each of these empty seats, figure out the distance to the closest person already sitting on the bench.
- Keep track of the largest of these distances.
- After checking every empty seat, the seat with the largest distance to the nearest person is our best choice.
Code Implementation
def max_dist_to_closest(seats):
max_distance = 0
for empty_seat_index in range(len(seats)):
if seats[empty_seat_index] == 0:
# Found an empty seat; now find closest person.
min_person_distance = float('inf')
for person_index in range(len(seats)):
if seats[person_index] == 1:
distance = abs(empty_seat_index - person_index)
min_person_distance = min(min_person_distance, distance)
# Keep track of the maximum closest distance.
max_distance = max(max_distance, min_person_distance)
return max_distance
Big(O) Analysis
Time Complexity
O(n²) – We iterate through each of the n seats on the bench, identifying empty seats. For each empty seat, we must find the closest occupied seat. Finding the closest occupied seat requires iterating through the entire array again in the worst case to calculate distances to all other people. This nested iteration results in approximately n * n operations. Therefore, the time complexity is O(n²).
Space Complexity
O(1) – The provided plain English explanation does not explicitly mention any auxiliary data structures like arrays, lists, or hash maps. It describes iterating through empty seats and calculating distances, which can be done using a few constant-sized variables to store the maximum distance found so far and the index of the best seat. Therefore, the auxiliary space used is constant, independent of the number of seats (N), making the space complexity O(1).
Optimal Solution
Approach
The goal is to find the largest possible gap between a seat and the nearest person. We can solve this efficiently by scanning the row of seats to find the sizes of all the empty spaces and then choosing the largest one, while paying special attention to the ends.
Here's how the algorithm would work step-by-step:
- First, find all the empty spaces at the very beginning of the row and record the size of that space.
- Next, go through the row of seats, looking for empty spaces between people. Calculate the size of each empty space. If the space is between two people, we can only use half the seats in this space (rounded down) to maximize the distance to the nearest person.
- Finally, look at the empty space at the very end of the row and record its size.
- Compare all the empty space sizes you've found (the space at the beginning, half the space in between, and the space at the end), and choose the largest one. That's the maximum distance to the closest person you can achieve.
Code Implementation
def max_dist_to_closest(seats):
max_distance = 0
last_person_position = -1
# Handle empty seats at the beginning
for i, seat in enumerate(seats):
if seat == 1:
max_distance = i
last_person_position = i
break
elif i == len(seats) - 1:
max_distance = len(seats) #All seats are empty
return max_distance
# Find empty seats between people
for i in range(last_person_position + 1, len(seats)):
if seats[i] == 1:
distance = i - last_person_position - 1
# Distance is halved because person can sit in the middle
max_distance = max(max_distance, distance // 2 + (distance % 2))
last_person_position = i
# Handle empty seats at the end
max_distance = max(max_distance, len(seats) - 1 - last_person_position)
return max_distanceBig(O) Analysis
Time Complexity
O(n) – The algorithm scans the array of seats (of size n) a fixed number of times: once to find the leading empty space, once to iterate through the seats finding intermediate empty spaces, and implicitly when considering the trailing empty space. Each scan iterates through the array once, performing constant-time operations at each seat. Therefore, the time complexity is directly proportional to the number of seats, n, resulting in O(n).
Space Complexity
O(1) – The algorithm only uses a few variables to keep track of the maximum distance found so far, the beginning distance, and the end distance. No auxiliary data structures like arrays or hash maps are created. The amount of extra memory used does not depend on the size of the input array of seats (N), remaining constant. Therefore, the space complexity is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty input array | Return 0 or throw an IllegalArgumentException, based on requirements, since there are no seats. |
| Input array with only one element | Return 0 since the problem states there is at least one empty seat and one person. |
| Input array with all seats occupied (all 1s) | Return 0 since there must be at least one empty seat. |
| Input array with all seats empty (all 0s) | Return the length of the array, as the maximum distance would be from either end. |
| Empty seat at the beginning of the array | Track the distance from the beginning to the first occupied seat, and update the maximum distance accordingly. |
| Empty seat at the end of the array | Track the distance from the last occupied seat to the end, and update the maximum distance accordingly. |
| Multiple consecutive empty seats in the middle of the array | Calculate half the distance between the surrounding occupied seats and update the maximum distance if necessary. |
| Large input array size (potential performance bottleneck) | Ensure the solution uses a linear time complexity algorithm (O(n)) to efficiently iterate through the seats array. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
