We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximize Distance to Closest Person

Difficulty: Medium

Problem Description

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the i-th seat, and seats[i] = 0 represents that the i-th 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.

Key Insights

  • The goal is to find the maximum distance to the closest occupied seat from any empty seat.
  • The distance to the closest person should be calculated for each empty seat.
  • The maximum distance can be influenced by the positions of the occupied seats at the edges of the array as well as between occupied seats.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can utilize a linear scan through the array to determine the maximum distance to the nearest person. The algorithm involves the following steps:

  1. Iterate through the array to identify all occupied seats and calculate the distances to the nearest occupied seat for each empty seat.
  2. Keep track of the distance to the nearest occupied seat from both directions (left and right) using two pointers.
  3. The maximum of these distances will be the desired output.

The primary data structure used is a simple array to represent the seats, and we compute indices during the traversal without needing extra space for a separate structure.

Code Solutions

def maxDistToClosest(seats):
    max_distance = 0
    last_person_position = -1
    n = len(seats)

    for i in range(n):
        if seats[i] == 1:
            if last_person_position == -1:  # First person found
                max_distance = i  # Distance from the start to the first person
            else:
                # Distance to the closest person is half the distance between two persons
                max_distance = max(max_distance, (i - last_person_position) // 2)
            last_person_position = i

    # Check distance from the last person to the end of the row
    max_distance = max(max_distance, n - 1 - last_person_position)
    
    return max_distance
← Back to All Questions