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.
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
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.