Условие

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

Примеры

Input: arr = [1, 0, 2, 3, 0, 4, 5, 0] Output: [1, 0, 0, 2, 3, 0, 0, 4] Explanation: После вызова функции входной массив изменится на указанный выше.

Input: arr = [1, 2, 3] Output: [1, 2, 3] Explanation: Входной массив не изменится, так как в нём нет нулей.

Решение

fun duplicateZeros(arr: IntArray) {
    var zeros = 0
    val n = arr.size

    // Считаем количество нулей, которые поместятся после дублирования
    for (num in arr) {
        if (num == 0) zeros++
    }

    var i = n - 1
    var j = n + zeros - 1

    // Идем с конца, расставляем числа и дублируем нули
    while (i < j) {
        if (j < n) arr[j] = arr[i]  // Копируем число на новую позицию

        if (arr[i] == 0) {
            j--
            if (j < n) arr[j] = 0  // Дублируем ноль
        }
        i--
        j--
    }
}

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

O(n), где n — количество элементов массива.

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

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