Pascal's Triangle
Generate the first numRows rows of Pascal's triangle bottom-up: every row starts and ends with 1, and each inside value is the sum of the two above.
Problem Understanding
Pascal's Triangle: given numRows, return the first numRows rows of Pascal's triangle. In the triangle, each number is the sum of the two numbers directly above it.
Example: numRows = 5 returns [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].
The Intuition: Each Row Comes From the One Above
This is dynamic programming at its simplest: a value is built from two smaller answers that are already known.
- Row 0 is
[1]. - Every later row starts and ends with
1. - Each inside value is
prev[j − 1] + prev[j], the two values above it.
Nothing older than the previous row is ever needed, the same one-step dependency as Climbing Stairs. The numbers in row n are the binomial coefficients C(n, k), which is why the triangle also counts paths in a grid, as in Unique Paths.
Interactive Walkthrough
The triangle grows one value at a time. For an inside value, the two values above it that were added are tinted. Try Seven rows to see the binomial coefficients 1, 6, 15, 20, 15, 6, 1 appear.
Dry Run Table
Input: numRows = 5
| Row | Built from | Row |
|---|---|---|
| 0 | — | [1] |
| 1 | edges only | [1, 1] |
| 2 | 1 + 1 | [1, 2, 1] |
| 3 | 1 + 2, 2 + 1 | [1, 3, 3, 1] |
| 4 | 1 + 3, 3 + 3, 3 + 1 | [1, 4, 6, 4, 1] |
The Solution Template
Build each row from the previous one.
Pascal's Triangle Code
1var generate = function(numRows) {2 const rows = [[1]];3 for (let r = 1; r < numRows; r++) {4 const prev = rows[r - 1], row = [1];5 for (let j = 1; j < r; j++) row.push(prev[j - 1] + prev[j]);6 row.push(1);7 rows.push(row);8 }9 return rows;10};
Edge Cases & Common Mistakes
- numRows = 1: return
[[1]]; the loop does not run. - Row 1:
[1, 1]has no inside values; the inner loop runs zero times. - Off-by-one on the inner loop: inside positions are
1 … r − 1; positions 0 and r are the edges. - Reusing the same row object: in Java and JavaScript, create a new list for each row instead of mutating the previous one.
- Pascal's Triangle II (LeetCode 119): to return only row k in O(k) space, update a single array from right to left:
row[j] += row[j − 1].
Summary
Start with [1]. Each new row begins and ends with 1, and every inside value is the sum of the two values above it. Repeat for numRows rows. O(n²) time and space, which is the size of the output.
More practice: DSA interview questions with answers · patterns cheat sheet