✏️ Расстояния между единицами: находим нужный паттерн

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

Массив [1,0,0,0,1,0,0,1] при k=2 валиден: между первой и второй единицей три нуля (достаточно), между второй и третьей — два нуля (достаточно). А вот [1,0,1,0,0,1] при k=2 — нет, потому что первые две единицы разделены только одним нулём.

Запоминаем позицию последней найденной единицы. Когда встречаем новую, проверяем расстояние до неё и сразу обновляем позицию.

Это будет один проход по массиву:

func kLengthApart(nums []int, k int) bool {
    lastPos := -k - 1
    
    for i := 0; i < len(nums); i++ {
        if nums[i] == 1 {
            if i - lastPos - 1 < k {
                return false
            }
            lastPos = i
        }
    }
    return true
}

Результат: O(n) время, O(1) память.

📍 Навигация: Вакансии • Задачи • Собесы

🐸 Библиотека Go-разработчика

#ReadySetGo