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), 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

Solution

Two Pointer - left, i

left - 为左侧为1的位置下标，i不断向右侧寻找下一个位置为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/

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 另一种思路

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/