Pattern visualizer

Pascal's Triangle

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. Animated on: numRows = 5 — generate the first 5 rows of Pascal's Triangle..

Each cell is the sum of the two cells above it

time O(numRows^2)space O(numRows^2)step 1 / 5

[0]

line 2

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

Where to practice Arrays

Practice Arrays problems All Arrays problems Back to roadmap