849. Maximize Distance to Closest Person

leetcode medium

#array#csharp#leetcode#math#medium#two-pointers

Task

Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).

Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.

Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.

Верните это максимальное расстояние до ближайшего человека.

Пример:

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.

C# solution

matched/original

public 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;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxDistToClosest(vector<int>& seats) {
        int n = seats.size();
        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 = max(ans, min(left, right));
            }
        }
        return ans;
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

var maxDistToClosest = function(seats) {
    let n = seats.length;
    let prev = -1, future = 0;
    let ans = 0;

    for (let i = 0; i < n; ++i) {
        if (seats[i] === 1) {
            prev = i;
        } else {
            while (future < n && (seats[future] === 0 || future < i)) {
                future++;
            }
            let left = prev === -1 ? n : i - prev;
            let right = future === n ? n : future - i;
            ans = Math.max(ans, Math.min(left, right));
        }
    }

    return ans;
};

Python solution

matched/original

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        n = len(seats)
        prev = -1
        future = 0
        ans = 0

        for i in range(n):
            if seats[i] == 1:
                prev = i
            else:
                while future < n and (seats[future] == 0 or future < i):
                    future += 1
                left = n if prev == -1 else i - prev
                right = n if future == n else future - i
                ans = max(ans, min(left, right))
        
        return ans

Go solution

matched/original

func maxDistToClosest(seats []int) int {
    n := len(seats)
    prev := -1
    future := 0
    ans := 0

    for i := 0; i < n; i++ {
        if seats[i] == 1 {
            prev = i
        } else {
            for future < n && (seats[future] == 0 || future < i) {
                future++
            }
            left := n
            if prev != -1 {
                left = i - prev
            }
            right := n
            if future != n {
                right = future - i
            }
            ans = max(ans, min(left, right))
        }
    }

    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

Найдите и верните максимальное расстояние до ближайшего занятого места.

😎