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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Distance to Closest Person

Number: 879

Difficulty: Medium

Paid? No

Companies: Yandex, Roblox, Samsung, Amazon, Tinkoff, Snap, Google

Problem Description

Given an array of seats where seats[i] = 1 represents an occupied seat and seats[i] = 0 represents an empty seat, find the maximum distance to the closest person if you choose an optimal empty seat. The goal is to maximize the distance between your chosen seat and the nearest occupied seat.

Key Insights

  • Identify three types of gaps:
    • The gap at the beginning of the array (before the first occupied seat).
    • The gap in the middle between two occupied seats.
    • The gap at the end of the array (after the last occupied seat).
  • For the middle gaps, the maximum distance is half of the gap length (using integer division).
  • Use a single pass to track the previous occupied seat and update the maximum distance accordingly.
  • After iterating, ensure to consider the gap from the last occupied seat to the end of the row.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the seats array. Space Complexity: O(1) since only a few extra variables are used.

Solution

We solve the problem by iterating through the seats array and updating a variable to store the index of the last occupied seat. For each occupied seat encountered:

  • If it’s the first occupied seat (prev is -1), the potential maximum distance from the left end is the index value.
  • Otherwise, compute the half-distance between the current and previous occupied seats. After the loop, update the maximum distance considering the gap from the last occupied seat to the end of the row. This approach ensures that all possible gaps are considered.

Code Solutions

def maxDistToClosest(seats):
    max_distance = 0      # Maximum distance initialized to zero
    prev = -1             # Previous occupied seat index
    n = len(seats)        # Total number of seats
    
    # Iterate through each seat in the row
    for i, seat in enumerate(seats):
        if seat == 1:
            if prev == -1:
                # Left edge gap: distance from start to first occupied seat
                max_distance = i
            else:
                # Middle gap: half the distance between consecutive occupied seats
                max_distance = max(max_distance, (i - prev) // 2)
            prev = i  # Update previous occupied seat index
    
    # Right edge gap: distance from last occupied seat to the end of the row
    max_distance = max(max_distance, n - 1 - prev)
    return max_distance

# Example usage:
print(maxDistToClosest([1,0,0,0,1,0,1]))  # Expected output: 2
← Back to All Questions