STEP 3 · ARRAYS · COUNTING THE LAST STEP · EASY

Pascal's Triangle

WHAT IT SAYS

Build the first numRows rows of Pascal's triangle, where every interior number is the sum of the two numbers above it.

WHAT IT'S REALLY ASKING

"Ask what each cell is actually counting: the number of ways to walk down to it from the apex. Now ask how any such walk ARRIVED — its final step came from the cell above-left or the cell above-right, and there is no third door. The sum rule is not a rule to memorise; it is a headcount."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Compute each entry from the factorial formula

O(n^2) cells, each costing O(n) multiplications, and enormous intermediates

The cell in row n, position r is the binomial coefficient n! / (r! * (n-r)!). Loop over every cell and evaluate it directly.

WHERE THE WORK IS WASTED — Two specific crimes. First, the intermediates dwarf the answers: to produce the number 6 you compute 4! = 24 and then divide almost all of it away, and by row 21 the factorial has blown past a 64-bit integer while the answer it is trying to express still fits comfortably. You are overflowing on the way to a small number. Second, the whole triangle depends on only n distinct factorials, and you recompute them from 1 upwards for every one of the n^2 cells.

KEY OBSERVATION — THE UNLOCKlink

Every path here came through one of exactly two doors.

Read a cell as a count: how many ways can you get from the tip of the triangle to here, stepping down-left or down-right each time? Take any such path and look only at its last step. It arrived either from the cell up-and-left or the cell up-and-right. Those two families of paths are disjoint — they differ in that final step, so no path is in both — and they are exhaustive, since there is nowhere else a step could have come from. When you split a set into disjoint, exhaustive parts, the sizes add. So the count here equals the count above-left plus the count above-right. That is Pascal's rule, derived rather than declared. And the consequences are exactly what you wanted. The recurrence only ever adds, so no intermediate value is ever bigger than the final answer — the overflow problem is not mitigated, it is structurally impossible. Each row depends solely on the row above it, so you need no factorials, no division, and no lookups further back than one row. The edges take care of themselves: there is exactly one way to reach a cell on the boundary (never turn), so the border is all 1s — that is the base case, and it is a fact about paths, not a special case you bolt on.

KEY OBSERVATION — THE UNLOCKlink

You can also walk sideways along a single row.

The vertical recurrence is optimal for building the whole triangle, but it is a terrible way to answer 'give me only row 20', because it forces you to construct rows 1 through 19 as scaffolding and then throw them away. So look for a recurrence that runs ALONG a row. Compare two neighbours in row n: C(n, r) / C(n, r-1) simplifies, after the factorials cancel, to (n - r + 1) / r. Which means each entry is its left neighbour times (n - r + 1), divided by r. So a row is one left-to-right sweep starting from 1: multiply, divide, print, repeat. No previous row, no factorial, O(n) time and O(1) extra state. And the arithmetic stays exact in integers provided you multiply BEFORE you divide — the running product C(n, r-1) * (n - r + 1) is always divisible by r, because it is r times an integer binomial coefficient. Reverse the order and you are doing floating-point division on a value that is supposed to be exact.

Pick the recurrence that matches the question

Whole triangle: O(n^2) time. One row: O(n) time, O(1) extra space. One cell at (n, r): O(r) time.

For the whole triangle, run the vertical rule: each new row starts and ends with 1, and every interior cell is the sum of the two cells above it — O(n^2) time, which is optimal because the output itself has n^2 numbers in it. For a single row, run the horizontal rule: start at 1 and repeatedly multiply by (n - r + 1) and divide by r. For a single cell, run the horizontal rule and stop early.

WHAT YOU TRADED — The vertical rule buys exact, overflow-free integer arithmetic at the cost of building every row you did not ask for; the horizontal rule skips straight to the row you want but reintroduces a division, whose exactness depends on you never reordering the operations. The transferable lesson: when a table's cells are counts of paths, the recurrence is just a case analysis on the last step — and you should always ask whether you need the whole table or only one line of it.

WATCH THE IDEA RUN

doors into a cell 2

additions used 0

factorials computed 0

The first cell of any row is 1, and not by decree: there is exactly one way to reach the left edge, which is to never once step right.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Count the Last Step

YOU'LL SEE IT AGAIN WHEN

A value counts the number of ways to reach a state, and the state has a small fixed set of predecessors — so the count splits into a disjoint sum.
You reach for a closed form whose intermediates (factorials, powers) are vastly larger than the answer they produce.
You only need one row, one cell, or one layer of a table — which means constructing the entire table is scaffolding you should try to delete.

SAME BLUEPRINT, DIFFERENT PROBLEM

Unique PathsClimbing StairsPascal's Triangle II (single row)Triangle (Minimum Path Sum)

The bar isn't "solved it once." It's "could rebuild it from the observation."