Algorithm

Pascal's Triangle

Arrays & Strings Pattern

Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

CONSTRAINTS
  • 1 <= numRows <= 30
EXAMPLE 1
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Each interior element is the sum of the two elements above it.
EXAMPLE 2
Input: numRows = 1
Output: [[1]]
First row is always just [1].
EXAMPLE 3
Input: numRows = 3
Output: [[1],[1,1],[1,2,1]]
Row 2: 1+1=2 in the middle.
Just to clarify the output format, you want an array of arrays representing the whole triangle, not just a specific row?
Correct, you should return a list containing all the rows up to `numRows`.
Are the values in the triangle guaranteed to fit within a standard 32-bit signed integer?
Yes, `numRows` is small enough (<= 30) that you do not need to worry about integer overflow.

Building Pascal's Triangle means generating a series of rows where each number is the sum of the two numbers centered directly above it. The challenge is to compute these values efficiently without recalculating the same "parent" numbers over and over.

Recursive Inefficiency (Exponential)

The most basic way to find any cell (row, col) is to recursively call a function for the two cells above it. However, this is incredibly slow because it recalculates the same cells thousands of times.

python
def get_val(r, c):
    if c == 0 or c == r: return 1
    return get_val(r-1, c-1) + get_val(r-1, c)
2. The Insight: Dynamic Programming

Instead of recomputing the same values, we can build the triangle row-by-row. Every number we calculate is stored in a list, so when we move to the next row, its "parents" are already waiting for us in memory.

Row-by-Row DP (O(N²))

We build the triangle iteratively.
- The first and last elements of every row are always 1.
- For every middle index, the value is the sum of prev[j-1] + prev[j].

python
triangle = [[1]]
for i in range(1, num_rows):
    prev = triangle[i-1]
    curr = [1]
    for j in range(1, i):
        curr.append(prev[j-1] + prev[j])
    curr.append(1)
    triangle.append(curr)
return triangle
Worked Example:numRows = 4
1
We start by initializing the first row of Pascal's Triangle with the single value 1.
1
1
1
We generate the second row by adding boundary values of 1 at both the start and the end.
1
1
1
1
2
1
We build the third row by placing boundary values of 1 at the edges, and calculating the middle cell by summing the two numbers directly above it (1 plus 1 equals 2).
1
1
1
1
2
1
1
3
3
1
We generate the fourth row by summing the adjacent pairs from the previous row to find the middle values (1 plus 2 is 3, and 2 plus 1 is 3) and capping the row with 1s.
Interactive Strategy Visualization

Triangle Construction

Dynamic Programming Strategy
Click Play to generate the triangle
RECURRENCE RELATION

Each cell (i, j) = Cell (i-1, j-1) + Cell (i-1, j). This symmetry builds the entire structure from the edges inward.

EFFICIENCY

We process O(N²) cells in total. By building layer by layer, we avoid redundant calculations—the core of Dynamic Programming.

Exponential Recursion
→
O(numRows²) Row-by-Row — Optimal (output is that size)