605. Can Place Flowers

Задача

У вас есть длинная цветочная клумба, на которой некоторые участки засажены, а некоторые — нет. Однако цветы нельзя сажать на смежных (соседних) участках.

Дан целочисленный массив flowerbed (клумба), содержащий 0 и 1, где 0 означает, что участок пуст, а 1 — что он не пуст, и целое число n. Верните true, если на клумбе можно посадить n новых цветов, не нарушая правило «нет смежных цветов», и false в противном случае.

Примеры

Пример 1

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

Пример 2

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

Решение

Решение

/**
 * Временная сложность: O(N) - один проход по массиву.
 * Пространственная сложность: O(1) - меняем массив in-place или просто считаем.
 */
var canPlaceFlowers = function(flowerbed, n) {
    for (let i = 0; i < flowerbed.length; i++) {
        // Если уже посадили всё, что нужно - выходим досрочно
        if (n <= 0) return true;
 
        // Проверяем текущую ячейку
        if (flowerbed[i] === 0) {
            // Проверяем соседей (безопасно для границ массива)
            const prevEmpty = (i === 0) || (flowerbed[i - 1] === 0);
            const nextEmpty = (i === flowerbed.length - 1) || (flowerbed[i + 1] === 0);
 
            if (prevEmpty && nextEmpty) {
                // Сажаем цветок
                flowerbed[i] = 1;
                n--;
 
                // Оптимизация: следующий точно нельзя занять, пропускаем его
                // (i++ сработает в цикле, и мы перескочим через один)
                i++;
            }
        }
    }
 
    return n <= 0;
};