Algorithm to Maximize Social Distancing

You are given a list of integers seats containing 1s and 0s. Each element seats[i] represents a seat and is either occupied if seats[i] = 1 or empty if seats[i] = 0.

Given that there is at least one empty seat, return the maximum distance from an empty seat to the closest occupied seat.
Constraints
n ≤ 100,000 where n is the length of seats
Example 1
Input
seats = [1, 0, 1, 0, 0, 0, 1]
Output
2
Explanation
We can sit at seats[4].

Example 2
Input
seats = [1, 0, 0, 0]
Output
3
Explanation
We can sit at seats[3].

Social Distance Algorithm

If the current seat is empty, we can compute the minimal distance to its nearest seats in both left and right direction. And if we go through each empty seats, we want to maximize the distance we can get.

We can use two arrays to store the nearest occupied seat in both left and right direction respectively. This preprocessing takes O(N) time and O(N) space. And once we have these, we iterate the array in O(N) to compute the maximum distance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int maxSocialDistance(vector<int>& seats) {
    int n = seats.size();
    if (n == 0) return 0;
    vector<int> left(n), right(n);
    int prev = -INT_MAX + 1;
    for (int i = 0; i < n; ++ i) {
        if (seats[i] == 0) {
            left[i] = prev;
        } else {
            prev = i;
            left[i] = i;
        }
    }
    prev = INT_MAX;
    for (int i = static_cast<int>(n) - 1; i >= 0; -- i) {
        if (seats[i] == 0) {
            right[i] = prev;
        } else {
            prev = i;
            right[i] = i;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++ i) {
        ans = max(ans, min(i - left[i], right[i] - i));
    }
    return ans;
}

int maxSocialDistance(vector<int>& seats) {
    int n = seats.size();
    if (n == 0) return 0;
    vector<int> left(n), right(n);
    int prev = -INT_MAX + 1;
    for (int i = 0; i < n; ++ i) {
        if (seats[i] == 0) {
            left[i] = prev;
        } else {
            prev = i;
            left[i] = i;
        }
    }
    prev = INT_MAX;
    for (int i = static_cast<int>(n) - 1; i >= 0; -- i) {
        if (seats[i] == 0) {
            right[i] = prev;
        } else {
            prev = i;
            right[i] = i;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++ i) {
        ans = max(ans, min(i - left[i], right[i] - i));
    }
    return ans;
}

–EOF (The Ultimate Computing & Technology Blog) —