Pascal's Triangle

Each cell is the sum of the two cells above it

time O(numRows^2)space O(numRows^2)

Every row's two edges are always 1 (there's only one way to reach the corner of a triangle), and every interior cell counts the paths converging into it from the row above — which is exactly the sum of the two cells diagonally above it. Building row by row, each new row only needs the row directly before it, never anything older.

Details

Animated on: numRows = 5 — generate the first 5 rows of Pascal's Triangle.

Problem:Pascal's TriangleEasy

Each cell is the sum of the two cells above it

step 1 / 5

[0]

Row 0 is always [1] — the only cell with no cells above it, the base case. Every other cell is the sum of the two cells diagonally above it.

Pseudocode

1FUNCTION pascalsTriangle(numRows):
2  start rows with a single first row [1]
3  FOR i from 1 to numRows-1:
4    make row = a list of 1s of length i+1
5    FOR j from 1 to i-1:
6      set row[j] to rows[i-1][j-1] + rows[i-1][j]   (sum of the two cells above)
7    append row to rows
8  RETURN rows

← / → step · space play · Home restart

Every step in words

Show all 5 steps

Row 0 is always [1] — the only cell with no cells above it, the base case. Every other cell is the sum of the two cells diagonally above it.
Row 1: edges are always 1; each middle cell = row[0][j-1] + row[0][j]. Row 0 was [1] -> row 1 is [1,1].
Row 2: edges are always 1; each middle cell = row[1][j-1] + row[1][j]. Row 1 was [1,1] -> row 2 is [1,2,1].
Row 3: edges are always 1; each middle cell = row[2][j-1] + row[2][j]. Row 2 was [1,2,1] -> row 3 is [1,3,3,1].
Row 4: edges are always 1; each middle cell = row[3][j-1] + row[3][j]. Row 3 was [1,3,3,1] -> row 4 is [1,4,6,4,1].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Pascal's Triangle in the editor All Arrays problems Back to roadmap