W
← Blog/dsaarraysdynamic-programming

Pascal's Triangle — From Combinatorics to DP Mastery [Easy]

Sanjeev SharmaSanjeev Sharma
13 min read

Advertisement

Problem Statement

LeetCode 118 — Pascal's Triangle

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.

Example:

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

Row 0:        1
Row 1:       1 1
Row 2:      1 2 1
Row 3:     1 3 3 1
Row 4:    1 4 6 4 1

Why This Problem Matters

Pascal's Triangle is one of the best first DP problems because the recurrence relation is completely obvious from the visual structure. You can see with your own eyes that every interior cell is the sum of the two cells above it — there is no guesswork, no tricky state definition, and no multi-dimensional array needed for the transition.

That simplicity makes it the perfect bridge from "I've heard of dynamic programming" to "I understand what DP actually means." The structure teaches you three foundational DP habits at once:

  1. Build on previously computed results. Each row depends entirely on the previous row. You never recompute anything from scratch.
  2. Think in terms of subproblems. Generating row i is a subproblem of generating row i+1. Solve smaller cases first, store them, build up.
  3. Identify base cases explicitly. The first and last element of every row are always 1. Recognizing invariants like these is a core DP skill that carries directly into harder problems like Unique Paths, Edit Distance, and Longest Common Subsequence.

Beyond DP, this triangle sits at the intersection of combinatorics, probability, algebra, and number theory — making it one of the most studied mathematical objects of all time.

The Mathematical Background

Every element in Pascal's Triangle is a binomial coefficient. Specifically, the element in row n at column k (both zero-indexed) equals:

triangle[n][k] = C(n, k) = n! / (k! × (n-k)!)

This is read as "n choose k" — the number of ways to choose k items from n items without regard to order. A few concrete examples from row 4:

C(4,0) = 1    ← the leading 1
C(4,1) = 4    ← 4 ways to pick 1 from 4
C(4,2) = 6    ← 6 ways to pick 2 from 4
C(4,3) = 4
C(4,4) = 1    ← the trailing 1

The DP recurrence triangle[n][k] = triangle[n-1][k-1] + triangle[n-1][k] is just Pascal's Rule for binomial coefficients:

C(n, k) = C(n-1, k-1) + C(n-1, k)

Why does this identity hold? Imagine you have n items and you want to choose k of them. Fix one special item — call it item X. Every valid selection either includes X (then you choose the remaining k-1 from the other n-1 items → C(n-1, k-1) ways) or excludes X (then you choose all k from the other n-1 items → C(n-1, k) ways). Add them together and you get C(n, k). That combinatorial argument is exactly what the triangle's addition rule encodes visually.

This connection means Pascal's Triangle isn't just a coding exercise — it is a concrete, visual proof of Pascal's Rule that you can point to in any interview.

The DP Approach

The algorithm is a direct translation of the recurrence:

Step 1: Start with an empty result list.

Step 2: For each row i from 0 to numRows - 1:

  • Create a new row of length i + 1, initialized entirely to 1.
  • Loop through interior positions j from 1 to i - 1 (exclusive on both ends).
  • Set row[j] = prev_row[j-1] + prev_row[j].
  • Append the row to the result.

Why initialize to 1? Because the first and last positions are always 1. By filling the whole row with 1 upfront, the loop only needs to handle interior positions — clean and minimal code.

Why loop from j = 1 to j < i? Position 0 and position i are the edge elements, which stay 1. The interior range is [1, i-1] inclusive, which in a half-open loop is range(1, i) or j = 1; j < i.

The Interesting Properties

Understanding these properties makes your blog posts and interview answers far more compelling — and some of them appear directly in other LeetCode problems:

1. Row sum = 2^n The sum of all elements in row n (zero-indexed) is exactly 2^n. Row 0 sums to 1 = 2^0, row 1 sums to 2 = 2^1, row 4 sums to 1+4+6+4+1 = 16 = 2^4. The proof: in (1+1)^n = 2^n, the binomial theorem expands to the sum of all C(n,k) — exactly the elements of row n.

2. Fibonacci numbers appear in shallow diagonals If you draw the triangle left-justified and sum along diagonal bands running upper-right to lower-left, the sums are 1, 1, 2, 3, 5, 8, 13, ... — the Fibonacci sequence. This is a non-trivial identity that surprises people every time.

3. The Hockey Stick identity Pick any element on the left edge (a 1), go diagonally down-right for any number of steps, then turn and go one step down-left. The last element equals the sum of all elements you visited on the diagonal. This is used to derive closed-form formulas for sums like 1 + 2 + 3 + ... + n = C(n+1, 2).

4. Powers of 11 Row 0 = 1 = 11^0. Row 1 = 11 = 11^1. Row 2 = 121 = 11^2. Row 3 = 1331 = 11^3. Row 4 = 14641 = 11^4. It breaks down for row 5 because of carrying, but the pattern holds for the first five rows.

5. Symmetry Each row is a palindrome: C(n, k) = C(n, n-k). This is because choosing k items to include is equivalent to choosing n-k items to exclude. You can exploit this symmetry in LC 119 to halve your computation.

Pascal's Triangle II — Single Row in O(k) Space

LeetCode 119 asks for only the rowIndex-th row (zero-indexed) using at most O(rowIndex) extra space. There are two clean approaches:

Approach 1: In-Place Right-to-Left Update

Maintain a single array of length rowIndex + 1, initialized to all 1s. For each row from 2 to rowIndex, iterate the array from right to left and add arr[j] += arr[j-1]. Going right-to-left ensures you read the old value of arr[j-1] before overwriting it.

def getRow(rowIndex):
    row = [1] * (rowIndex + 1)
    for i in range(2, rowIndex + 1):
        for j in range(i - 1, 0, -1):  # right to left
            row[j] += row[j - 1]
    return row

Approach 2: Direct Formula — O(rowIndex) time, O(rowIndex) space

Use the recurrence between consecutive binomial coefficients:

C(n, k) = C(n, k-1) × (n - k + 1) / k

Start with C(n, 0) = 1 and compute each subsequent element in one pass:

def getRow(rowIndex):
    row = [1] * (rowIndex + 1)
    for k in range(1, rowIndex + 1):
        # C(rowIndex, k) = C(rowIndex, k-1) * (rowIndex - k + 1) / k
        row[k] = row[k - 1] * (rowIndex - k + 1) // k
    return row

This computes the entire row in a single loop with no inner loop at all — elegant and fast. The key insight is that the ratio between adjacent binomial coefficients is always a rational number that simplifies to an integer at each step.

Visual Dry Run

Let's trace numRows = 5 step by step:

i=0: row = [1]
     result = [[1]]

i=1: row = [1, 1]   (no interior positions — loop doesn't run)
     result = [[1], [1,1]]

i=2: row starts as [1, 1, 1]
     j=1: row[1] = result[1][0] + result[1][1] = 1 + 1 = 2
     row = [1, 2, 1]
     result = [[1],[1,1],[1,2,1]]

i=3: row starts as [1, 1, 1, 1]
     j=1: row[1] = result[2][0] + result[2][1] = 1 + 2 = 3
     j=2: row[2] = result[2][1] + result[2][2] = 2 + 1 = 3
     row = [1, 3, 3, 1]
     result = [[1],[1,1],[1,2,1],[1,3,3,1]]

i=4: row starts as [1, 1, 1, 1, 1]
     j=1: row[1] = 1 + 3 = 4
     j=2: row[2] = 3 + 3 = 6
     j=3: row[3] = 3 + 1 = 4
     row = [1, 4, 6, 4, 1]
     result = [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Notice how row 4 contains C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1 — verifying the binomial coefficient connection directly.

Common Mistakes

Mistake 1: Wrong loop range for interior elements

The most common bug is using range(0, i+1) for the interior loop instead of range(1, i). If you update row[0] or row[i], you overwrite the 1s that were supposed to stay fixed as boundary conditions.

# WRONG — overwrites boundary elements
for j in range(0, i + 1):
    row[j] = triangle[i-1][j-1] + triangle[i-1][j]  # index out of range at j=0

# CORRECT — only touches interior positions
for j in range(1, i):
    row[j] = triangle[i-1][j-1] + triangle[i-1][j]

Mistake 2: Off-by-one in row count

LeetCode says "generate the first numRows rows." The loop should run from i = 0 to i = numRows - 1 (i.e., range(numRows)), giving exactly numRows rows. Using range(1, numRows + 1) or range(numRows + 1) produces the wrong number of rows.

Mistake 3: Not initializing rows correctly before the inner loop

If you initialize row = [0] * (i + 1) and rely entirely on the inner loop to set all values, you must handle positions 0 and i explicitly. Forgetting to do so leaves the boundary elements as 0 instead of 1. The cleaner approach is to initialize row = [1] * (i + 1) and let the inner loop only touch interior positions.

Solutions

LeetCode 118 — Generate Pascal's Triangle

Python

def generate(numRows: int) -> list[list[int]]:
    triangle = []

    for i in range(numRows):
        # Initialize the entire row to 1 — handles edges automatically
        row = [1] * (i + 1)

        # Only update interior positions; edges stay 1
        for j in range(1, i):
            # Each interior element is the sum of the two elements above
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]

        triangle.append(row)

    return triangle

JavaScript

/**
 * @param {number} numRows
 * @return {number[][]}
 */
function generate(numRows) {
    const triangle = [];

    for (let i = 0; i < numRows; i++) {
        // Fill entire row with 1s — first and last are correct already
        const row = new Array(i + 1).fill(1);

        // Compute interior positions using the previous row
        for (let j = 1; j < i; j++) {
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }

        triangle.push(row);
    }

    return triangle;
}

LeetCode 119 — Return Only the k-th Row

Python — In-Place O(rowIndex) Space

def getRow(rowIndex: int) -> list[int]:
    # Single array, updated in place row by row
    row = [1] * (rowIndex + 1)

    # Start from row 2 (rows 0 and 1 are all 1s by initialization)
    for i in range(2, rowIndex + 1):
        # Traverse right to left so we read old values before overwriting
        for j in range(i - 1, 0, -1):
            row[j] += row[j - 1]

    return row

Python — Formula Approach (single pass)

def getRow(rowIndex: int) -> list[int]:
    row = [1] * (rowIndex + 1)

    # C(rowIndex, k) = C(rowIndex, k-1) * (rowIndex - k + 1) / k
    for k in range(1, rowIndex + 1):
        row[k] = row[k - 1] * (rowIndex - k + 1) // k

    return row

JavaScript — Formula Approach

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
function getRow(rowIndex) {
    const row = new Array(rowIndex + 1).fill(1);

    // Build using the ratio between adjacent binomial coefficients
    // C(n, k) = C(n, k-1) * (n - k + 1) / k
    for (let k = 1; k <= rowIndex; k++) {
        row[k] = Math.round(row[k - 1] * (rowIndex - k + 1) / k);
    }

    return row;
}

Complexity Analysis

LC 118 — Generate Full Triangle

TimeSpace
Building the triangleO(numRows²)O(numRows²)

The outer loop runs numRows times. Row i has i + 1 elements, so total work is 1 + 2 + 3 + ... + numRows = numRows × (numRows + 1) / 2 = O(numRows²). Space is the same because we store every element.

LC 119 — Single Row

ApproachTimeSpace
In-place row simulationO(rowIndex²)O(rowIndex)
Formula (single pass)O(rowIndex)O(rowIndex)

The formula approach is strictly better — it computes each element in O(1) with a single multiplication and division, requiring no inner loop at all.

Follow-Up Questions

LeetCode 62 — Unique Paths

A robot moves from the top-left to the bottom-right of an m × n grid, moving only right or down. The number of unique paths is C(m + n - 2, m - 1) — a single entry in Pascal's Triangle. The DP table for this problem is structurally identical to Pascal's Triangle: dp[i][j] = dp[i-1][j] + dp[i][j-1], with the boundary condition that the top row and left column are all 1.

LeetCode 63 — Unique Paths II

Same structure as LC 62, but some cells are blocked. You set dp[i][j] = 0 when a cell is an obstacle, and apply the same recurrence elsewhere. The Pascal's Triangle intuition — build from boundaries, combine adjacent cells — carries directly.

Triangle DP Pattern (LeetCode 120 — Triangle)

Given a triangle array, find the minimum path sum from top to bottom. The recurrence is dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j]) — the same row-by-row build, just with a different operation (min instead of sum). Recognizing the Pascal's Triangle shape in this problem is the key insight.

Coin Change Patterns

The unbounded knapsack / Coin Change family uses a similar "build up table row by row" pattern. Once you are comfortable with Pascal's Triangle, the leap to dp[i][j] = dp[i-1][j] + dp[i][j - coins[i]] feels natural rather than mysterious.

This Pattern Solves

Any problem where you fill a 2D DP table (or a triangular structure) row by row, where each cell depends only on the current or previous row:

  • Grid path counting problems (LC 62, 63)
  • Triangle minimum path sum (LC 120)
  • Problems asking for binomial coefficients explicitly
  • Probability distributions on a grid (random walk problems)
  • Generating combinations C(n, k) for large n without overflow (use the formula approach from LC 119)

Key Takeaway

Pascal's Triangle teaches the most important habit in dynamic programming: trust the recurrence. Once you see that every interior element is the sum of its two parents, the code writes itself — initialize boundaries to 1, loop over interior positions, read from the previous row, done. The deeper lesson is that this triangle is not just a coding exercise but a window into combinatorics: every element triangle[n][k] answers the question "in how many ways can I choose k items from n?" That connection recurs throughout algorithm problems — Unique Paths, coin combinations, probability trees — so internalizing it here pays dividends across your entire interview preparation.

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro

twitterlinkedingithubmail

← Previous

Valid Anagram — Frequency Array, HashMap & Sort [LeetCode 242]

Next →

Arrays & Strings Complete — 100-Problem Master Cheatsheet