Условие

Дан массив flowerbed, представляющий клумбу, где flowerbed[i] = 1 означает, что на позиции i уже есть цветок, а flowerbed[i] = 0 означает, что она свободна. Также дано целое число n. Вы должны определить, можно ли посадить n новых цветов, соблюдая правило: цветы не могут быть посажены на соседние позиции.

Примеры

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

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

Решение

fun canPlaceFlowers(flowerbed: IntArray, n: Int): Boolean {
    var count = 0 // Счетчик для количества посаженных цветов
    var i = 0

    while (i < flowerbed.size) {
        // Если текущая позиция свободна и соседние тоже свободны (или на краях массива)
        if (flowerbed[i] == 0 &&
            (i == 0 || flowerbed[i - 1] == 0) &&
            (i == flowerbed.size - 1 || flowerbed[i + 1] == 0)) {
            flowerbed[i] = 1 // Сажаем цветок
            count++ // Увеличиваем счетчик
            if (count >= n) return true // Если достигли нужного числа, возвращаем true
            i += 2 // Пропускаем следующую позицию
        } else {
            i++ // Переходим к следующей позиции
        }
    }
    return count >= n // Проверяем, удалось ли посадить нужное количество цветов
}

Временная сложность

O(m), где m — размер массива flowerbed.

Пространственная сложность

O(1), так как не используется дополнительная память.