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:
- Find the first occupied seat and mark the distance to the left as -1
- Find the next occupied seat and mark the distance to the right from the previous occupied seat as their mid-point distance.
- keep finding the next occupied seats and keep incrementing the mid-point distance until a new occupied seat is found.
- Maximize the Mid-point distance between the occupied seats.
Algorithm:
- Traverse the seats array from left to right and find the index of the first seat that is occupied
- Initialize left = -1 and max_dist = 0
- 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
- If the last seat is empty, update the value of max_dist = max(max_dist, len(seats) – 1 – left)
- 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; }