Pascal's Triangle

Условие

Дан целый параметр numRows. Необходимо построить первые numRows строк треугольника Паскаля.

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

Примеры

Input: numRows = 5

Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Input: numRows = 1

Output: [[1]]

Решение

fun generate(numRows: Int): List<List<Int>> {
    val triangle = mutableListOf<List<Int>>() // Инициализация пустого списка для хранения строк треугольника

    for (i in 0 until numRows) {
        val row = MutableList(i + 1) { 1 } // Создание новой строки, заполненной 1
        for (j in 1 until i) {
            // Каждое число является суммой двух чисел, находящихся сверху
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
        }
        triangle.add(row) // Добавление строки в треугольник
    }
    return triangle
}

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

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

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

O(n²), так как требуется хранить n строк треугольника Паскаля, каждая из которых увеличивается в размере.