Basic Problemscountingcombinatoricsgrid

Pascal's Triangle

Given a number of rows n, generate Pascal's Triangle: a triangular array where each interior entry equals the sum of the two entries diagonally above it, with 1s running along both outer edges.

Do this lesson first: climbing stairs

Example input

numRows = 8

Expected output

[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1]

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[r][k] is entry k of row r of the triangle, for 0 <= k <= r. That is binomial-coefficient's table, where the same cell is read as C(r, k), the number of ways to choose k items out of r; this page needs nothing from that reading, but it is why the entries are called binomial coefficients. Two numbers name a cell, its row and its position in the row. What changes from every neighbouring page is not the state but what counts as the answer: here it is EVERY cell of the table, so there is no cell to aim at and nothing to throw away afterwards.

dp[r][k] = dp[r - 1][k - 1] + dp[r - 1][k], for 0 < k < r

The statement hands you this rule, and it can give it outright because the triangle is defined by it. binomial-coefficient derives the same rule from a counting argument (single out one item; a selection either keeps it or drops it), and nothing in that derivation changes here. What is worth noticing on this page is the shape of the dependency rather than its origin: every interior entry needs exactly two entries of the row above, an adjacent pair, so a row can be written as soon as the row above it is finished, and never sooner.

dp[r][0] = 1 and dp[r][r] = 1 on every row: the two outer edges are 1s by definition. They have to be given rather than summed, because the rule would reach for column -1 at the left end and for a position above the diagonal at the right end, and neither exists. Row 0 is the single cell where the two edges meet. Fill row by row, top to bottom; within a row the interior entries do not read each other, so left to right is as good as any order. The positions above the diagonal show a dot: they are not part of the triangle, and no interior cell can reach one, since a cell at column k < r reads columns k - 1 and k of row r - 1, both on or below that row's diagonal.

Tabulation, one row-major sweep, and on this page the full table is the right price rather than the generous one. The output has numRows (numRows + 1) / 2 numbers, so no method can do better than O(numRows^2) time or space: the sweep's one addition per interior entry is already the cost of writing the answer down. That is the opposite of nth-row-of-pascals-triangle, which builds this same triangle to return its last row and spends its whole execution section on the cheaper ways to get there. Each of those ways throws away the rows above, and here the rows above are the output, so none of them applies. The closed form C(r, k) = r! / (k! (r - k)!) can fill any entry on its own, and it is how this page's correctness check works out every cell independently, but for building the triangle it is worse: worked out on its own, an entry takes up to k multiply-divide steps against one addition, which is O(numRows^3) over the whole triangle, and the in-row version of it, C(r, k) = C(r, k - 1) × (r - k + 1) / k, is still O(numRows^2) over the whole triangle.

Time O(numRows^2), one addition per interior entrySpace O(numRows^2), which is the size of the output itself

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[r][0] = 1 and dp[r][r] = 1 on every row: the two outer edges are 1s by definition. They have to be given rather than summed, because the rule would reach for column -1 at the left end and for a position above the diagonal at the right end, and neither exists. Row 0 is the single cell where the two edges meet. Fill row by row, top to bottom; within a row the interior entries do not read each other, so left to right is as good as any order. The positions above the diagonal show a dot: they are not part of the triangle, and no interior cell can reach one, since a cell at column k < r reads columns k - 1 and k of row r - 1, both on or below that row's diagonal.

Rows ↓
Cols →

0

1

2

3

4

5

6

7

0

1

·

1

·

2

1

2

1

·

3

1

3

1

·

4

1

4

6

4

1

·

5

1

5

10

5

1

·

6

1

6

15

20

15

6

1

·

7

1

7

21

35

21

7

1

Rows ↓row r: a row of the triangle, and every row is output

Cols →column k: entry k of its row

pascals-triangle.ts

1function generate(numRows) {
2 const rows = [];
3 for (let r = 0; r < numRows; r++) {
4 const row = new Array(r + 1);
5 row[0] = 1;
6 row[r] = 1;
7 for (let k = 1; k < r; k++) {
8 const upLeft = rows[r - 1][k - 1];
9 const up = rows[r - 1][k];
10 row[k] = upLeft + up;
11 }
12 rows.push(row);
13 }
14 return rows;
15}

Base caseComputedBeing readAnswer

The code, the trap, the variations

pascals-triangle.ts

1function generate(numRows) {
2 const rows = [];
3 for (let r = 0; r < numRows; r++) {
4 const row = new Array(r + 1);
5 row[0] = 1;
6 row[r] = 1;
7 for (let k = 1; k < r; k++) {
8 const upLeft = rows[r - 1][k - 1];
9 const up = rows[r - 1][k];
10 row[k] = upLeft + up;
11 }
12 rows.push(row);
13 }
14 return rows;
15}

Where people go wrong

Carrying nth-row-of-pascals-triangle's one-array trick over to this problem. There, a single array updated from the right turns each row into the next, and that is correct because only the last row is wanted. Here, pushing that one array into the result after each pass pushes the SAME array every time, so every row of the result is one object, and when the loop finishes they all show its final contents: at numRows = 8 the result is 1, 7, 21, 35, 35, 21, 7, 1 eight times over. Nothing throws and every number in it is a real entry of the triangle, which is what makes it easy to miss in a quick look at the last row. Push a copy each pass, or build a fresh row as the snippet does.

Return only the last row instead of every row.
That is nth-row-of-pascals-triangle. The recurrence, the given edges and the fill order do not change. What changes is that the rows above the last stop being output, so they can be dropped as soon as the next row is built: one rolling row is O(n) space, and walking across a single row with the in-row closed form is O(n) time as well.
Return a single entry, C(n, k), instead of any whole row.
That is binomial-coefficient: the same table, read at one cell. The sweep can then stop at column k, so the work is O(n k) rather than O(n^2), and everything right of column k is never written.
Generate the triangle modulo 2, keeping only whether each entry is odd.
Replace the addition with an exclusive or, or add and take % 2. The shape, the given edges and the order stay exactly as they are, and the odd entries trace out the Sierpinski triangle. The values stop growing at all, which is the point of reducing modulo anything: entries of row 34 already pass 2^31, and modulo a number the table never overflows.

Binomial Coefficient Nth Row of Pascal Triangle