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

Дан массив нулей и единиц, нужно проверить, что между любыми двумя единицами находится минимум 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) память.

#ReadySetGo

@goproglib