algoadvance

Leetcode 849. Maximize Distance to Closest Person

Problem Statement

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 to the closest person is maximized. Return that maximum distance to the closest person.

Clarifying Questions

  1. Can the input array seats be empty?
    • No, the problem guarantees at least one seat is empty and at least one seat is occupied.
  2. What should be returned if there are multiple seats with the same maximum distance?
    • The task is to return the distance itself, so it does not matter which seat gives that distance, only the maximum distance matters.
  3. Are there only two types of values in the array, 0 and 1?
    • Yes, seats can only be 0 (empty) or 1 (occupied).

Strategy

We can solve this problem in a single pass through the array. The strategy involves:

  1. Initialize a variable to keep track of the maximum possible distance, maxDist.
  2. Track the last occupied seat with a variable lastOccupied.
  3. Traverse the array from left to right:
    • When encountering an occupied seat (seats[i] == 1), update the distance for each segment.
    • Handle the special cases where there are leading or trailing zeros separately.
  4. For each empty segment between two occupied seats, calculate the potential maximum distance a person can sit at. This is half of the segment length (rounded down).

Finally, we need to handle the cases where the person can sit at the beginning of the row or at the end.

Code

Let’s implement this strategy in Java:

public class Solution {
    public int maxDistToClosest(int[] seats) {
        int n = seats.length;
        int maxDist = 0;
        int lastOccupied = -1;

        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (lastOccupied == -1) {
                    // Distance from the start of the row to this person
                    maxDist = i;
                } else {
                    // Distance between two people
                    maxDist = Math.max(maxDist, (i - lastOccupied) / 2);
                }
                lastOccupied = i;
            }
        }

        // Distance from the last person to the end of the row
        if (seats[n - 1] == 0) {
            maxDist = Math.max(maxDist, n - 1 - lastOccupied);
        }

        return maxDist;
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array seats. This is because we make a single pass through the array to calculate the maximum distance.

By following this approach, we efficiently determine the maximum distance Alex can sit from the closest person in linear time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI