medium Maximize Distance to Closest Person

Problem Statement

You are given a binary array seats representing the row of seats, where seats[i] = 0 represents that the i^th seat is empty, and seats[i] = 1 represents a person sitting in the i^th seat. It is given that seats array contains at least one 1 and 0.

You want to sit in any seat such that the distance between you and the closest person to you is maximized.

Return that maximum distance to the closest person.

Examples

• Example 1:

  • Input: seats = [1,0,0,0,1,0,0]
  • Expected Output: 2
  • Justification: The best seat is either of the two at the index 2 or 6, as they are both 2 seats away from the nearest occupied seat.

• Example 2:

  • Input: seats = [1,0,0,0,0,1]
  • Expected Output: 2
  • Justification: The middle seats (index 2 or 3) are equally optimal, being 2 seats away from any occupied seat.

• Example 3:

  • Input: seats = [0,1,0,1,0,1,0,0,0,0]
  • Expected Output: 4
  • Justification: The best position is at the end (index 9), which is 4 seats away from the nearest person.

Solution

To solve this problem, our approach focuses on calculating the distance between occupied seats and identifying the maximum gap for a person to sit. Initially, we'll scan the array to find the distances between all pairs of occupied seats. Additionally, we'll pay special attention to the edges of the array, where the distance calculation slightly varies because one side is bound by the array's end rather than another occupied seat. This method ensures we consider the maximum available distance at both the beginning and the end of the row.

The rationale behind this approach is that the optimal seat, in terms of distance to the closest person, is either between two occupied seats, at the beginning, or at the end of the row. By comparing these distances, we can determine the best seat. This method is effective because it directly calculates the relevant distances without unnecessary comparisons or iterations, making it efficient for solving the problem.

Step-by-step Algorithm

1. Initialize Variables:

   • maxDistance to keep track of the maximum distance to the closest person. Initially set to 0.
   • lastOccupied to track the index of the last occupied seat encountered while iterating through the array. Initially set to -1 as a marker that no occupied seat has been encountered yet.
   • n to store the length of the seats array.

2. Iterate Through the Seats:

   • Loop through each seat in the array using an index variable i.

3. Check if Seat is Occupied:

   • If the current seat (seats[i]) is occupied (== 1), proceed to calculate the distance to the nearest person.
   • If it's the first occupied seat encountered (lastOccupied == -1), the distance is i itself, because it's the distance from the start to the first occupied seat.
   • Otherwise, calculate the distance as (i - lastOccupied) / 2. This accounts for the distance between two occupied seats, effectively finding the midpoint which gives the maximum distance to the closest person.

4. Update lastOccupied:

   • Set lastOccupied to the current index i to mark the latest occupied seat.

5. Check Distance from Last Occupied Seat to End:

   • After the loop completes, check if the distance from the last occupied seat to the end of the array (n - 1 - lastOccupied) is greater than the current maxDistance.

6. Return maxDistance:

   • Return the maxDistance found as the maximum distance to the closest person.

Algorithm Walkthrough

Let's consider the input [0,1,0,1,0,1,0,0,0,0].

• Start:

  • maxDistance = 0, lastOccupied = -1, n = 10

• Iteration 0 (i = 0):

  • Seat is not occupied. No updates.

• Iteration 1 (i = 1):

  • Seat is occupied. lastOccupied = -1 initially, so lastOccupied is updated to 1. Update maxDistance to 1

• Iteration 2 (i = 2):

  • Seat is not occupied. No updates.

• Iteration 3 (i = 3):

  • Seat is occupied. Calculate distance: (3 - 1) / 2 = 1. maxDistance remains 1. Update lastOccupied to 3.

• Iteration 4 (i = 4):

  • Seat is not occupied. No updates.

• Iteration 5 (i = 5):

  • Seat is occupied. Calculate distance: (5 - 3) / 2 = 1. maxDistance remains 1. Update lastOccupied to 5.

• Iterations 6 to 9:

  • Seats are not occupied until the end. No updates to maxDistance or lastOccupied during these iterations.

• After Loop:

  • Check distance from last occupied to end: 9 - 5 = 4. Since 4 is greater than maxDistance, update maxDistance to 4.

• End:

  • maxDistance = 4 is returned as the maximum distance to the closest person.

Code

public class Solution {

  // Method to find the maximum distance to the closest person
  public int maxDistToClosest(int[] seats) {
    int maxDistance = 0; // To keep track of the maximum distance
    int lastOccupied = -1; // To keep track of the last occupied seat
    int n = seats.length; // Total number of seats

    // Iterate through the array to find the maximum gap
    for (int i = 0; i < n; i++) {
      if (seats[i] == 1) {
        // For the first occupied seat, distance is i itself
        // For others, calculate the distance from the last occupied seat
        maxDistance = lastOccupied == -1
          ? i
          : Math.max(maxDistance, (i - lastOccupied) / 2);
        lastOccupied = i; // Update the last occupied seat index
      }
    }
    // Check the distance from the last occupied seat to the end of the row
    maxDistance = Math.max(maxDistance, n - 1 - lastOccupied);

    return maxDistance;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the method with the provided examples
    System.out.println(
      solution.maxDistToClosest(new int[] { 1, 0, 0, 0, 1, 0, 0 })
    ); // Expected output: 2
    System.out.println(
      solution.maxDistToClosest(new int[] { 1, 0, 0, 0, 0, 1 })
    ); // Expected output: 2
    System.out.println(
      solution.maxDistToClosest(new int[] { 0, 1, 0, 1, 0, 1, 0, 0, 0, 0 })
    ); // Expected output: 4
  }
}

Complexity Analysis

Time Complexity:

The algorithm iterates through the array exactly once to calculate the maximum distance to the closest person. Hence, the time complexity is linear with respect to the number of seats, n.

Space Complexity:

The space complexity is constant because the solutions use a fixed amount of space regardless of the input size.