Pascal's Triangle II

Условие

Дано целое число rowIndex, необходимо вернуть строку Паскаля, которая находится на позиции rowIndex (индексация начинается с 0).

В треугольнике Паскаля каждая строка представляет собой список, где каждый элемент является суммой двух чисел, расположенных выше этого элемента в предыдущей строке.

Примеры

Input: rowIndex = 3

Output: [1, 3, 3, 1]

Explanation: Третья строка треугольника Паскаля равна [1, 3, 3, 1].

Input: rowIndex = 0

Output: [1]

Explanation: Нулевая строка треугольника Паскаля равна [1].

Input: rowIndex = 1

Output: [1, 1]

Explanation: Первая строка треугольника Паскаля равна [1, 1].

Решение

fun getRow(rowIndex: Int): List<Int> {
    // Инициализация строки с первым элементом 1
    val row = mutableListOf(1)
    
    // Для каждой строки от 1 до rowIndex
    for (i in 1..rowIndex) {
        // Добавляем элемент 1 в конец строки
        row.add(0)  // Для сдвига всех элементов
        // Обновляем значения в строке начиная с конца
        for (j in i downTo 1) {
            row[j] = row[j] + row[j - 1]
        }
    }
    return row
}

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

O(n²), где n — индекс строки. Для каждой строки мы обновляем элементы, что занимает время пропорционально её длине.

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

O(n), так как нам нужно хранить только одну строку треугольника с индексом n.