LeetCode 118 · Recursion · DP

Pascal’s Triangle, explained with a picture

Stacking oranges in a triangle.

Recursion · DP
▶ Watch it step by step

The problem

Generate the first numRows rows of Pascal’s triangle, where each number is the sum of the two above it.

Input:  6 rows
Output: [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1], [1,5,10,10,5,1]

Picture it

Picture oranges stacked into a triangle. Each orange rests on two below it… or, read top-down, each new row is built from the row above: the edges are 1, and every inside number is the sum of the two numbers above it.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

row[i] = prev[i − 1] + prev[i]. O(rows²).

Python solution

def generate(n):
    rows = [[1]]
    for i in range(1, n):
        prev = rows[-1]
        row = [1]
        for j in range(1, i):
            row.append(prev[j - 1] + prev[j])
        row.append(1)
        rows.append(row)
    return rows

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.