849. Maximize Distance to Closest Person

tags: subarray, two pointers
source: leetcode

Edge Cases

Solution 1 - divide by situations

start is 0 -> max dis: number of 0
end is 0 -> max dis: number of 0
group of 0 between 1 -> max dis: (number of 0 + 1) / 2

class Solution {
    public int maxDistToClosest(int[] seats) {
        int zero = 0, maxDis = 0;

        for (int i = 0; i < seats.length && seats[i] == 0; i++) zero++;
        maxDis = zero;

        zero = 0;
        for (int i = seats.length - 1; i >= 0 && seats[i] == 0; i--) zero++;
        maxDis = Math.max(zero, maxDis);

        for (int i = 0; i < seats.length; i++) {
            if (seats[i] == 1) {
                zero = 0;
            } else {
                zero++;
                maxDis = Math.max((zero + 1) / 2, maxDis);
            }
        }

        return maxDis;
    }
}

Complexity

time: O(N)
space: O(1)

Solution 2 - two pinters

left is distance of current seat to left 1 right is distance of current seat to right 1

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

        for (int i = 0; i < N; ++i) {
            if (seats[i] == 1) {
                prev = i;
            } else {
                while (future < N && seats[future] == 0 || future < i)
                    future++;

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

        return ans;
    }
}

Complexity

time: O(N)
space: O(1)