Pascal's Triangle
Return the first numRows rows of Pascal's triangle, where each interior number is the sum of the two directly above it.
Intuition
Every row starts and ends with 1, and each inner entry is built from the row above. So we generate row by row, reading the previous row to fill the current one.
Straight simulation of the definition: each interior entry is the sum of the two above it, and the edges are always 1. Pre-filling the row with ones handles both boundaries without any conditional, so the inner loop only touches the genuinely computed cells.
Approach
The formula approach, and why we avoid it
Each entry equals a binomial coefficient C(r, k), so you could compute every cell directly with factorials. It works, but factorials grow enormous, risk overflow, and waste effort recomputing values that are trivially related. The triangle's own recursive definition is both simpler and cheaper.
Every cell is the sum of the two above it
That's the defining property of Pascal's triangle: an interior entry row[j] equals prev[j−1] + prev[j], the two numbers diagonally above it. The first and last entry of every row are always 1 (there's nothing above-left or above-right). So if we have the previous row, we can build the current one with simple additions — no factorials anywhere.
Build row by row, bottom-up
Start each row r as [1] * (r+1) (handling both ends for free), then fill the interior positions 1..r−1 by reading the previous row, and append it. Because we always have row r−1 finished before starting row r, this is a clean bottom-up dynamic-programming build. Rows 0 and 1 have no interior to fill and emit [1] and [1,1] directly. O(numRows²) total — exactly the number of entries produced.
Solution & live demo
Common pitfalls
Looping the interior over the full row
for j in range(r + 1):
row[j] = triangle[r-1][j-1] + triangle[r-1][j]for j in range(1, r):
row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j]At j = 0, triangle[r-1][-1] wraps to the last element of the previous row instead of erroring, quietly corrupting the edge. The first and last entries are 1 by definition and must not be recomputed.
Reading from the row being built
row[j] = row[j - 1] + row[j]
row[j] = triangle[r - 1][j - 1] + triangle[r - 1][j]
Left-to-right, row[j-1] has already been overwritten with a new value, so the sum mixes the current row with the previous one. Read explicitly from the finished row above.
Computing entries with the factorial formula
row = [comb(r, j) for j in range(r + 1)]
row[j] = triangle[r-1][j-1] + triangle[r-1][j]
Mathematically right, but it recomputes large factorials for every cell and overflows in fixed-width languages. The additive recurrence is what the structure is for.
Edge cases
The inner fill loop has no range; the row is simply [1].
Rows 0 and 1 have no interior positions, so they emit [1] and [1,1] directly.
Because each row is mirror-symmetric, the same left-to-right fill produces correct right-side values automatically.