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 rowsIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.