Basic Problemscountingcombinatoricsgrid

Nth Row of Pascal Triangle

Given a row index n, return just that single row of Pascal's Triangle, without producing every row that comes above it.

Example input

n = 8

Expected output

1 8 28 56 70 56 28 8 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[n][k] is entry k of row n of Pascal's triangle, which is the number of ways to choose k items out of n. That is the SAME TABLE binomial-coefficient fills, cell for cell: same lower-triangular shape, same two given edges, same rule at every interior cell, same row-major order. One thing changed, and it is the question asked of the table. There, the input named a pair of counts and one cell answered it. Here the input names a row, so the answer is a WHOLE ROW: all n + 1 cells of the bottom row are output, and the sweep's final pass is the result rather than a step towards it. A reader arriving here first loses nothing by reading it in this order: a cell holds a count and nothing about which items were picked, and the two numbers labelling it, the row and the position within that row, are the whole of the state.

dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k]

Single out one of the n items and ask whether a selection of k contains it: the selections that keep it need k - 1 more from the other n - 1 items, the selections that drop it need all k from the other n - 1, no selection is in both groups and none is outside them, so the two counts add rather than compete. binomial-coefficient makes that argument in full, including why a counting problem sums where an optimization problem takes a min, and not one word of it changes here. What is worth adding is what the same rule says once you are after the whole row: row n is determined by row n - 1 ALONE, one adjacent pair of it at a time. The rule never reaches back further than a single row, so every row above that one is dead the moment the row below it has been written. That single observation is what the execution section below spends its whole length on.

dp[n][0] = 1 and dp[n][n] = 1 on every row, one way to choose nothing and one way to choose everything, and both must be given rather than summed because the cells the rule would reach for, column -1 at one end and a position above the diagonal at the other, are off the table. Now say what that means HERE, because it is not what it means on binomial-coefficient's page, where the bases are the two places the answer is not. TWO OF THE NUMBERS THIS PAGE RETURNS ARE BASES. The 1 at each end of row 8 was not worked out by the sweep, it was handed to it, and only the 7 interior entries of the answer row are computed at all. Of the 45 live cells at n = 8, 17 are given, one per row down the left edge and one per row past the first on the diagonal, and 28 are summed. The positions above the diagonal show a dot, meaning a position that does not exist rather than a zero, and nothing here could read one even by accident: a computed cell in row r at column k has k <= r - 1, so the two cells it reads are columns k - 1 and k of row r - 1, both on or below that row's own diagonal. The FILL ORDER is that page's order too, and it is what this page's whole objection is about. Row-major, top to bottom and left to right inside each row, is enough for the rule, though it is not the only order that would do (column-major satisfies the same dependencies), and it is exactly the order the statement objects to: reaching row 8 this way means writing all 36 cells of rows 0 through 7, and 21 of those are additions this order performs before the first interior entry of row 8 is reached. None of the 36 is wanted. The order is not wrong. It is the cost, and execution is where that gets settled.

Tabulation, one row-major sweep, and the job of this section is to price that sweep against what it returns, because the statement is asking for something cheaper. The table in front of you is O(n^2) time and O(n^2) space to produce n + 1 numbers: at n = 8 it declares 81 cells, writes 45 of them, performs 28 additions, and 9 numbers come out. There are three steps down from there, each cheaper than the last, and NONE of them changes the recurrence. ONE ROLLING ROW. A cell reads only the row above it, so the row above is the only thing worth keeping and the rest of the triangle can be dropped as soon as it has been used. That is O(n) space, still O(n^2) time, and it is the same reduction that applies to every page in this course whose cells reach exactly one row back. ONE ARRAY, UPDATED RIGHT TO LEFT. The rolling row does not even need a second buffer to write into. Overwrite it in place, starting at the right end and moving inwards, and every write lands on a value nobody still needs: the only other position that reads position k is position k + 1, and going right to left that one was written already. One array of n + 1 numbers and no copying. The direction is not a detail; it is the pitfall below. NO TABLE AT ALL. Neighbouring entries of a single row are related to each other directly, C(n, k) = C(n, k - 1) × (n - k + 1) / k, so once the leading 1 is written you can walk across the row multiplying and dividing, n steps for the whole of it. That is O(n) time and O(n) space, which is the size of the output itself, so nothing can beat it. At n = 8 that is 8 multiply-divide steps against the sweep's 28 additions; the ratio is (n - 1) / 2, which runs 1.5, 2, 2.5, 3, 3.5 across the slider's five sizes and grows without bound past them. SO WHAT IS THE TABLE STILL WORTH SHOWING FOR? Not for running: of the four it is the most expensive, the only one paying O(n^2) space, and it does not even buy a faster sweep for that, since the rolling row performs the identical 28 additions. A page that told you the table was how to do this would be wrong. Two things survive. First, it is the only one of the four that keeps its whole history on screen, so every entry's provenance is visible as one step straight up and one step up and to the left; the two rolling forms overwrite that history as they go, and the multiplicative walk hands back the same nine numbers with no additive provenance for any single one of them. Second, the additive rule survives changes that the closed form does not: ask for the row modulo a prime and the multiplicative step's division by k turns into a modular inverse, while the additive row needs a plus and a percent. Shift the arithmetic slightly, as the Stirling-number variation on binomial-coefficient's page does, and the in-row shortcut is what goes: a Stirling number has a closed form of its own, but neighbouring entries of one of its rows are not related by a single multiply-and-divide the way binomial coefficients are, so there is no walk across the row to reach for. One argument NOT to make here is exactness, which is the argument that carries that other page. The multiplicative walk does divide, but every value it settles on is a real binomial coefficient, and measured in JavaScript it first disagrees with the exact row at n = 55 against the additive sweep's n = 57. Two rows apart, on a page whose slider stops at 8, is not a reason to prefer either one.

Time O(n^2) additions to sweep the triangle down to row n, against O(n) multiply-divide steps for the in-row closed formSpace O(n^2) for the full table, O(n) with one rolling row, which is the size of the answer

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[n][0] = 1 and dp[n][n] = 1 on every row, one way to choose nothing and one way to choose everything, and both must be given rather than summed because the cells the rule would reach for, column -1 at one end and a position above the diagonal at the other, are off the table. Now say what that means HERE, because it is not what it means on binomial-coefficient's page, where the bases are the two places the answer is not. TWO OF THE NUMBERS THIS PAGE RETURNS ARE BASES. The 1 at each end of row 8 was not worked out by the sweep, it was handed to it, and only the 7 interior entries of the answer row are computed at all. Of the 45 live cells at n = 8, 17 are given, one per row down the left edge and one per row past the first on the diagonal, and 28 are summed. The positions above the diagonal show a dot, meaning a position that does not exist rather than a zero, and nothing here could read one even by accident: a computed cell in row r at column k has k <= r - 1, so the two cells it reads are columns k - 1 and k of row r - 1, both on or below that row's own diagonal. The FILL ORDER is that page's order too, and it is what this page's whole objection is about. Row-major, top to bottom and left to right inside each row, is enough for the rule, though it is not the only order that would do (column-major satisfies the same dependencies), and it is exactly the order the statement objects to: reaching row 8 this way means writing all 36 cells of rows 0 through 7, and 21 of those are additions this order performs before the first interior entry of row 8 is reached. None of the 36 is wanted. The order is not wrong. It is the cost, and execution is where that gets settled.

row index: only the bottom row is the answer, every row above it is scaffolding

0

1

2

3

4

5

6

7

8

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

·

8

1

8

28

56

70

56

28

8

1

column k: position within the row, holding C(n, k)

nth-row-of-pascals-triangle.ts

1function pascalsTriangleRow(n) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 for (let i = 0; i <= n; i++) {
4 dp[i][0] = 1;
5 dp[i][i] = 1;
6 for (let k = 1; k < i; k++) {
7 const keepIt = dp[i - 1][k - 1];
8 const dropIt = dp[i - 1][k];
9 dp[i][k] = keepIt + dropIt;
10 }
11 }
12 return dp[n];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

nth-row-of-pascals-triangle.ts

1function pascalsTriangleRow(n) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 for (let i = 0; i <= n; i++) {
4 dp[i][0] = 1;
5 dp[i][i] = 1;
6 for (let k = 1; k < i; k++) {
7 const keepIt = dp[i - 1][k - 1];
8 const dropIt = dp[i - 1][k];
9 dp[i][k] = keepIt + dropIt;
10 }
11 }
12 return dp[n];
13}

Where people go wrong

Updating the single rolling row from the LEFT. It is the one step of the reduction that has a direction, and going the wrong way fails silently: nothing throws, the values stay whole numbers, and they are simply the wrong whole numbers. Writing row[k] = row[k] + row[k - 1] with k running upwards means position k - 1 has already been overwritten with the new row's value by the time position k reads it, so the cell adds its NEW left neighbour instead of the old one the rule asked for. At n = 8 that returns 1, 8, 35, 110, 275, 572, 1001, 1430, 1430 where the row is 1, 8, 28, 56, 70, 56, 28, 8, 1: too large from column 2 rightwards, no longer symmetric, and no longer even ending in a 1. What makes this survive a glance is that the wrong numbers are not noise. Run the broken loop for n = 1 through 8 and its last entry comes out 1, 2, 5, 14, 42, 132, 429, 1430, which are the Catalan numbers, so what comes back is a real and recognisable integer sequence rather than obvious garbage. Run the inner loop downwards from k = i instead and every cell reads the old value it wanted, with no second buffer. A smaller trap worth naming: the 1s at the two ends of the row are given, not computed, so a loop that tries to compute every entry of row n uniformly will ask for column -1 at one end and a position above the diagonal at the other.

Return the whole triangle down to row n instead of just row n.
Nothing about the recurrence, the bases or the fill order moves, and the O(n^2) sweep on this page stops being the wasteful choice: every cell it writes is now part of the answer, so the output has grown to the size of the table and the objection this whole page is built around disappears. Both reductions above die with it, because neither the rolling row nor the in-row closed form keeps the rows it has already finished. This is a catalog problem in its own right, pascals-triangle, and it is left statement-only rather than authored for a reason worth knowing: its answer is the entire table, so there is no single cell to highlight and no answer cell an independent check could ever disagree with.
Return row n modulo a prime p, the usual competitive-programming form.
Take a % p after each addition and every cell stays below p, which removes the overflow question entirely and leaves shape, bases, order and dependency arrows untouched. This is also the variation that makes the table worth keeping rather than the closed form: the in-row step divides by k, and dividing modulo p means multiplying by the modular inverse of k, which is real extra machinery to get right. The additive row needs a plus and a percent.
Ask for a single entry of the row rather than the whole row.
That is binomial-coefficient, the same table read at one highlighted cell instead of across the bottom row, and as problems they differ in nothing else. The two PAGES differ in one thing, which is what they open the slider at: 6 there against 8 here, so that two neighbouring pages never show the same grid. Going that way also revives a reduction this page cannot use: a sweep that only needs column k can stop at that column, which is O(n k) rather than O(n^2). The whole row needs every column of the bottom row, so it needs the whole triangle, and O(n k) with k = n is O(n^2) again.

Pascal's Triangle