Solution For Maximize Distance To Closest Person

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
4. 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
5. Set the value of left = right and continue the traversal
6. If the last seat is empty, update the value of max_dist = max(max_dist, len(seats) – 1 – left)
7. 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

Step by Step Implementation For Maximize Distance To Closest Person

class Solution {
    public int maxDistToClosest(int[] seats) {
        int max = 0;
        int prev = -1;
        for (int i = 0; i < seats.length; i++) {
            if (seats[i] == 1) {
                if (prev == -1) {
                    max = i;
                } else {
                    max = Math.max(max, (i - prev) / 2);
                }
                prev = i;
            }
        }
        max = Math.max(max, seats.length - 1 - prev);
        return max;
    }
}

Assuming the input is an array of integers representing the seats in the theatre:

def max_distance(arr):
    # initialize max_distance to 0
    max_distance = 0

    # iterate through the array
    for i in range(len(arr)):
        # if the current element is 0 (empty seat)
        if arr[i] == 0:
            # set j equal to i + 1
            j = i + 1
            # initialize count to 1
            count = 1
            # while the next element is also 0
            while j < len(arr) and arr[j] == 0:
                # increment count
                count += 1
                # increment j
                j += 1
            # if count is odd
            if count % 2 == 1:
                # set max_distance to the max of max_distance and count // 2
                max_distance = max(max_distance, count // 2)
            # otherwise
            else:
                # set max_distance to the max of max_distance and count // 2
                max_distance = max(max_distance, count // 2)
    return max_distance

var maxDistToClosest = function(seats) {
    // initialize max to first non-zero index
    let max = seats.indexOf(1);
    // iterate through seats
    for (let i = 0; i < seats.length; i++) {
        // if seat is zero
        if (seats[i] === 0) {
            // check if there is a one to the left
            if (seats[i-1] === 1) {
                // check if there is a one to the right
                if (seats[i+1] === 1) {
                    // set max to the smaller of max and (i - left) / 2
                    max = Math.min(max, Math.floor((i - left) / 2));
                } else {
                    // set max to the larger of max and i - left
                    max = Math.max(max, i - left);
                }
            } else {
                // set max to the larger of max and (right - i) / 2
                max = Math.max(max, Math.floor((right - i) / 2));
            }
        }
        // if seat is one
        if (seats[i] === 1) {
            // set left to i
            left = i;
        }
    }
    // return max
    return max;
};

There are a number of ways to approach this problem. One simple way would be to keep track of the maximum distance between any two people, and return that value.

int maxDistToClosest(vector& seats) { int max_dist = 0; for (int i = 0; i < seats.size(); i++) { int j = i + 1; while (j < seats.size() && seats[j] != 1) { j++; } if (j < seats.size()) { // There is a person at seat j max_dist = max(max_dist, (j - i) / 2); } else { // There are no more people max_dist = max(max_dist, j - i); } } return max_dist; }

public int MaxDistToClosest(int[] seats) {
    // max is the maximum distance between two people
    int max = 0;
    // start and end will keep track of the first and last person's position
    int start = 0, end = 0;
    
    // Iterate through the array
    for(int i = 0; i < seats.Length; i++) {
        // If the seat is empty, continue
        if(seats[i] == 0) {
            continue;
        }
        // Otherwise, we found a person
        else {
            // end is now equal to the position of the person
            end = i;
            // If the start is not equal to the end, that means there is a distance between the two people
            if(start != end) {
                // We find the middle of the two people by taking the average of the start and end
                int middle = (start + end) / 2;
                // We then find the maximum distance by taking the difference of the middle and the start
                max = Math.Max(max, middle - start);
            }
            // We then set the start to be the position of the next person
            start = i;
        }
    }
    // Finally, we return the maximum distance
    return max;
}