Pascal's Triangle
Easy · Arrays & Hashing · Array · Dynamic Programming
Problem
Pascal's triangle is built row by row. The first row is [1]. Every later row starts and ends with 1, and each value in between is the sum of the two values directly above it in the previous row.
Given an integer numRows, return the first numRows rows of the triangle as a list of lists.
Examples
Input: numRows = 4 Output: [[1],[1,1],[1,2,1],[1,3,3,1]]
The fourth row is 1, then 1 + 2 = 3 and 2 + 1 = 3, then 1.
Input: numRows = 1 Output: [[1]]
Only the first row, [1], is asked for.
Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
The fifth row adds neighboring pairs of [1,3,3,1]: 4, 6, 4.
Constraints
- 1 <= numRows <= 30
Approaches
- Baseline: compute every value from the binomial formula — time O(numRows³), space O(numRows²) for the output
Follow-up
If only row k were wanted, one list of length k + 1 is enough: update it in place from right to left, so each entry still reads the old value to its left. And any single entry is the binomial coefficient C(r, c), which a short multiplicative loop computes without any rows at all.
Related problems
Start free on Cariara · Coding problems · System design studio
