[leetcode #849] Maximize Distance to Closest Person

Problem

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

Example 1:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

Input: seats = [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat (i.e. seats[3]), the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Example 3:

Input: seats = [0,1]
Output: 1

Constraints:

・ 2 <= seats.length <= 2 * 10⁴
・ seats[i] is 0 or 1.
・ At least one seat is empty.
・ At least one seat is occupied.

Idea

Alex가 다른 승객들로부터 가장 멀리 떨어진 자리에 앉았을 때 거리를 구하는 문제다.

승객들이 앉은 상태인 seats를 왼쪽과 오른쪽으로 각각 탐색하면서 떨어진 거리를 먼저 구한다. 이 때 시작점에 승객이 없을 경우 거리를 주어진 조건의 최대값인 20,000으로 정한다.

왼쪽과 오른쪽 거리를 구한 뒤 두 값을 비교하여 최소값을 거리로 정한다. 이 때 정한 거리들 중 최대가 되는 값이 Alex가 가장 멀리 떨어진 자리에 앉았을 때의 거리가 된다.

Solution

class Solution {
    public int maxDistToClosest(int[] seats) {
        int[] left = new int[seats.length];
        int[] right = new int[seats.length];
        int distance = 20_000;

        for (int i=0; i < seats.length; i++) {
            if (seats[i] == 1) {
                distance = 0;
            } else {
                distance++;
            }
            left[i] = distance;
        }

        distance = 20_000;
        for (int i=seats.length-1; i >= 0; i--) {
            if (seats[i] == 1) {
                distance = 0;
            } else {
                distance++;
            }
            right[i] = distance;
        }

        int res = 0;
        for (int i=0; i < seats.length; i++) {
            distance = Math.min(left[i], right[i]);
            res = Math.max(res, distance);
        }

        return res;
    }
}

Reference

https://leetcode.com/problems/maximize-distance-to-closest-person/