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-based index).

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 Alex only sit in empty seats?
    • Yes, Alex can only sit in seats represented by 0.
  2. Should the distance be measured in terms of seat indices?
    • Yes, the distance to the closest person is measured as the difference in indices.
  3. Are there any constraints on the size of the array?
    • The number of seats will be at least 2 and at most 20,000.

Strategy

  1. Traverse through the array and locate each position of 1 (where a person is sitting).
  2. Track the maximum distance to the nearest person for every empty seat (0).
  3. Consider edge cases where the empty seats are at the beginning or end of the row.

Step-by-step approach:

  1. Initialize variables to store the previous and current maximum distances.
  2. Iterate through the array:
    • Each time a 1 is found, update the distance for the zeroes between the previous one and the current one.
  3. Update distances for any leading zeroes before the first 1 and trailing zeroes after the last 1.

Code

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int maxDistToClosest(vector<int>& seats) {
    int n = seats.size();
    int last_person = -1;
    int max_dist = 0;

    for (int i = 0; i < n; ++i) {
        if (seats[i] == 1) {
            if (last_person != -1) {
                // Case where we're between two people.
                int dist = (i - last_person) / 2;
                max_dist = max(max_dist, dist);
            } else {
                // Case where we have leading zeroes.
                max_dist = i;
            }
            last_person = i;
        }
    }

    // Case where we have trailing zeroes.
    if (last_person != -1) {
        max_dist = max(max_dist, n - last_person - 1);
    }

    return max_dist;
}

Time Complexity

In summary, this solution efficiently computes the maximum distance to the closest person by considering both the cases of leading and trailing zeroes with respect to seated people, ensuring that Alex can find the optimal seat.

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