Skip to main content

118 - Pascal's Triangle

Difficulty: Easy | Pattern: Simulation / DP | Company tags: Amazon, Apple, Google

Problem Statement​

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.

Example:

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

Visual:

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Solution​

def generate(numRows: int) -> list[list[int]]:
    triangle = []
    for row_idx in range(numRows):
        row = [1] * (row_idx + 1)  # all 1s initially
        for j in range(1, row_idx):  # inner elements (not first or last)
            row[j] = triangle[row_idx-1][j-1] + triangle[row_idx-1][j]
        triangle.append(row)
    return triangle

Algorithm Flow​

Dry Run​

RowInitialAfter filling innerFinal row
0[1](no inner)[1]
1[1,1](no inner)[1,1]
2[1,1,1]row[1]=1+1=2[1,2,1]
3[1,1,1,1]row[1]=1+2=3, row[2]=2+1=3[1,3,3,1]
4[1,1,1,1,1]row[1]=1+3=4, row[2]=3+3=6, row[3]=3+1=4[1,4,6,4,1]

Why Pascal's Triangle Matters​

Pascal's triangle encodes:

  • Binomial coefficients: Row n, position k = C(n, k) = n! / (k! * (n-k)!)
  • Powers of 11: Row 1=[1,1] → 11; Row 2=[1,2,1] → 121; Row 4=[1,4,6,4,1] → 14641
  • Fibonacci numbers: Sum of diagonal elements

Return only the k-th row (0-indexed) using O(k) space:

def getRow(rowIndex: int) -> list[int]:
    row = [1] * (rowIndex + 1)
    for i in range(1, rowIndex + 1):
        for j in range(i-1, 0, -1):  # go right to left to avoid overwriting
            row[j] += row[j-1]
    return row

Complexity​

  • Time: O(numRows²) — each row has proportional length
  • Space: O(numRows²) — storing the whole triangle