Как определить максимальную длину подмассива единиц после удаления одного элемента без дополнительной памяти за линейное время

Что проверяют

Узнаете ли вы классическую задачу на скользящее окно и доведёте ли её до верного ответа на краевых случаях. Удалить элемент нужно обязательно, и следом почти всегда спрашивают, что вернуть для массива из одних единиц.

Как отвечать

Переформулируйте условие: ищем самое длинное окно, в котором не больше одного нуля. Удаляемый элемент лежит внутри окна, поэтому ответ равен длине окна минус один. Это же закрывает случай «одни единицы»: удалить всё равно придётся одну из них.

Каркас на Swift:

func longestSubarray(_ nums: [Int]) -> Int {
    var left = 0, zeros = 0, best = 0
    for right in nums.indices {
        if nums[right] == 0 { zeros += 1 }
        while zeros > 1 {
            if nums[left] == 0 { zeros -= 1 }
            left += 1
        }
        best = max(best, right - left)
    }
    return best
}

Проговорите сложность: left и right проходят массив не больше одного раза каждый, поэтому время O(n), хотя внутри есть while. Дополнительная память O(1): три целых числа.

Альтернатива без окна: хранить длину текущей серии единиц и предыдущей, на каждом нуле переносить текущую в предыдущую, ответ это максимум их суммы. Тогда массив без нулей придётся обработать отдельно.

Прогоните примеры вслух: для [1, 1, 0, 1] ответ 3, для [1, 1, 1] ответ 2, для [0, 0, 0] ответ 0, для пустого массива тоже 0.

Где спотыкаются

Берут длину окна целиком, right - left + 1. Тогда ноль засчитывается как единица, и на [1, 1, 0, 1, 1] получается 5 вместо 4.

Забывают, что удаление обязательно, и для [1, 1, 1] отвечают 3.

Называют решение с вложенным while квадратичным или не могут объяснить, почему оно линейное. Интервьюер почти всегда просит это обосновать.