Дан ряд мест в кинотеатре, представленный массивом. Зритель выбирает свободное место так, чтобы максимизировать расстояние до ближайшего занятого места. Необходимо вычислить это максимальное расстояние (гарантировано: в ряду есть хотя бы одно занятое и хотя бы одно свободное место).

Задача сводится к поиску максимального расстояния от любого свободного места до ближайшего занятого. Решение — найти для каждого свободного места расстояние до ближайшего занятого слева и справа, взять минимум из них, а затем выбрать максимум из этих минимумов по всем свободным местам.

Алгоритм за O(n) с двумя проходами без дополнительной памяти (если не считать пару переменных):

def maxDistToNearestOccupied(seats):
    n = len(seats)
    # первый проход: расстояние до ближайшего занятого слева
    left = [0] * n
    last = -1  # индекс последнего занятого
    for i in range(n):
        if seats[i] == 1:
            last = i
            left[i] = 0
        else:
            if last == -1:
                left[i] = float('inf')
            else:
                left[i] = i - last
    # второй проход: расстояние до ближайшего занятого справа
    right = [0] * n
    last = -1
    for i in range(n-1, -1, -1):
        if seats[i] == 1:
            last = i
            right[i] = 0
        else:
            if last == -1:
                right[i] = float('inf')
            else:
                right[i] = last - i
    # третий проход: для каждого свободного места минимум из left и right
    ans = 0
    for i in range(n):
        if seats[i] == 0:
            d = min(left[i], right[i])
            if d > ans:
                ans = d
    return ans

Сложность: O(n) по времени, O(n) по памяти (можно сделать O(1) памяти, если хранить только текущие расстояния, но код станет менее читаемым). Для небольших массивов дополнительная память не критична.

Пример: seats = [1,0,0,0,1,0,1]. Проходы дадут left[2]=2, right[2]=2 -> min=2; left[3]=3, right[3]=1 -> min=1; left[5]=1, right[5]=1 -> min=1. Максимум = 2.

На краях (если первый или последний элемент свободный) расстояние считается только с одной стороны — это учтено через float('inf') и потом min выберет конечное расстояние.

Альтернатива: найти все блоки свободных мест между занятыми. Для внутреннего блока длины L максимальное расстояние = ceil(L/2) = (L+1)//2. Для краевых блоков — просто длина. Затем взять максимум по всем блокам. Этот способ компактнее, но требует аккуратного выделения блоков.