Maximize Distance to Closest Person

Easy

In a row ofseats,1represents a person sitting in that seat, and0represents that the seat is empty.

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 closest person.

Example 1:

Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (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: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:

1. 1 <= seats.length <= 20000

2. seats contains only 0s or 1s, at least one 0, and at least one 1

Analysis

用 Two Pointer解法，time - O(N), space O(1)

Solution

Two Pointer - left, i

left - 为左侧为1的位置下标，i不断向右侧寻找下一个位置为1的下标

注意初始值的设定：left = -1

class Solution {
    public int maxDistToClosest(int[] seats) {
        int left = -1;
        int maxDist = 0;
        for (int i = 0; i < seats.length; i++) {
            if (seats[i] == 0) {
                continue;
            }

            if (left < 0) {
                // when left of i is all empty seats     
                maxDist = Math.max(maxDist, i);
            } else {
                // left of i has a seat filled
                maxDist = Math.max(maxDist, (i - left) / 2);
            }
            left = i;
        }

        // when the right end side is empty
        if (seats[seats.length - 1] == 0) {
            maxDist = Math.max(maxDist, seats.length - 1 - left);
        }
        return maxDist;
    }
}

*(Preferred) Two Pointer 同一种思路的另一种实现：

https://www.jiuzhang.com/solution/maximize-distance-to-closest-person/

更简明清晰：i是外层循环，不断寻找被占用的座位(seats[i] == 1)，lastPerson记录左侧最近的人的位置，当i

找到下一个位置seats[i] == 1时，来计算当前的lastPerson ~ i到这个区间内的closest person的distance。用getDist() 函数很好地封装了这个距离的计算，特殊情况，即lastPerson == -1, i == seats.lengthy 也能被考虑到；一般情况就是(i - lastPerson) / 2.

当然，最后在for循环外，还要检验一下右侧全0的情况，防止遗漏。

class Solution {
    private int size;

    public int maxDistToClosest(int[] seats) {
        size = seats.length;
        int lastPerson = -1;
        int ans = 0;

        for (int i = 0; i < size; i++) {
            if (seats[i] == 1) {
                ans = Math.max(ans, getDist(lastPerson, i));
                lastPerson = i;
            }
        }
        ans = Math.max(ans, getDist(lastPerson, size));
        return ans;
    }

    private int getDist(int s, int e) {
        if (s == -1 || e == size) {
            return e - s - 1;
        } else {
            return (e - s) / 2;
        }
    }
}

Two Pointer 另一种思路

这种思路也比较清晰：分别记录i的左右两侧的被占用的座位prev, next，选择其较小者（也就是closest person）参与全局的max distance比较。

但是还是要处理左侧全0，或者右侧全0的情况。

Keep track of prev, the filled seat at or to the left of i, and next, the filled seat at or to the right of i.

Then at seat i, the closest person is min(i - prev, next - i), with one exception. i - prev should be considered infinite if there is no person to the left of seat i, and similarly next - i is infinite if there is no one to the right of seat i.

class Solution {
    public int maxDistToClosest(int[] seats) {
        int prev = -1, next = 0;
        int n = seats.length;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                // find filled seat at or to the left of i
                prev = i;
            } else {
                // find filled seat at or to the right of i 
                while (next < n && seats[next] == 0 || next < i) {
                    next++;
                }

                int left = prev == -1 ? n : i - prev;
                int right = next == n ? n : next - i;
                ans = Math.max(ans, Math.min(left, right));
            }
        }
        return ans;
    }
}

Reference

https://www.jiuzhang.com/solution/maximize-distance-to-closest-person/

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