# 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;
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]