Maximize Distance To Closest Person - Leetcode Solution

Problem Statement: You are given an array representing the seats in a row. The seats[i] contains 0 or 1, where 0 represents an empty seat and 1 represents a person sitting in that seat. 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 closest person.

Solution:

Approach:

1. Find the first occupied seat and mark the distance to the left as -1
2. Find the next occupied seat and mark the distance to the right from the previous occupied seat as their mid-point distance.
3. keep finding the next occupied seats and keep incrementing the mid-point distance until a new occupied seat is found.
4. Maximize the Mid-point distance between the occupied seats.

Algorithm:

1. Traverse the seats array from left to right and find the index of the first seat that is occupied
2. Initialize left = -1 and max_dist = 0
3. Traverse the seats array from left to right starting from the first occupied seat
   • If the current seat is occupied update the midpoint distance between the current occupied seat and the last occupied seat (midpoint = (right - left)//2) and check if this distance is greater than the max_dist, if yes then update the value of max_dist = midpoint
   • Set the value of left = right and continue the traversal
4. If the last seat is empty, update the value of max_dist = max(max_dist, len(seats) - 1 - left)
5. Return the value of max_dist

Time Complexity: The time complexity of the above algorithm is O(n) because we are only traversing the array once.

Space Complexity: The space complexity of the above algorithm is O(1) because we are not using any extra space.

Here is the python code to implement the above algorithm:

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        #find the index of the first seat that is occupied
        left = -1
        max_dist = 0
        for i in range(len(seats)):
            if seats[i] == 1:
                left = i
                break
        #check if the first seat is empty
        if left == -1:
            return 0
        #traverse the array to find the other occupied seats and calculate the mid-distance
        for i in range(left+1, len(seats)):
            if seats[i] == 1:
                right = i
                distance = (right - left)//2
                if distance > max_dist:
                    max_dist = distance
                left = right
        #check if the last seat is empty
        max_dist = max(max_dist, len(seats) - 1 - left)
        return max_dist              

1