Pascal's Triangle

The key idea

Every entry equals the sum of the two entries directly above it: row[i][j] = prev[j-1] + prev[j]. The two outer edges of every row are always 1 (there is no number above one side), so only the interior entries are computed — each from the row you just finished.

Problem

Given an integer numRows, return the first numRows rows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it. The first and last number of every row is 1, because one of the two numbers above an edge position is missing.

Constraints

1 <= numRows <= 30

Examples

Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Input: numRows = 1 Output: [[1]]

Complexity

Time: O(n^2) Space: O(n^2)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →