14.13 Pascal’s Triangle

14.13.1 Problem Metadata

14.13.2 Description

Given a non-negative integer numRows, generate the first numRows rows of Pascal’s triangle. Each number is the sum of the two numbers directly above it.

14.13.3 Examples

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

14.13.4 Constraints

  • 0 <= numRows <= 30

14.13.5 Solution - Dynamic Programming (Tabulation)

14.13.5.1 Walkthrough

This solution uses bottom-up dynamic programming (see Tabulation) to construct Pascal’s Triangle iteratively. Each row depends only on the previous row, making it a classic example of tabulation DP.

Core Strategy:

Pascal’s Triangle exhibits optimal substructure: each element is computed from elements in the previous row:

triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]

Base case: Row 0 contains a single element [1].

Recurrence relation: - First and last elements of each row are always 1 - Interior elements: row[j] = prevRow[j-1] + prevRow[j]

Why This is Dynamic Programming:

  • Optimal Substructure: Each row is built from the previous row’s values
  • Overlapping Subproblems: Each element uses values computed in the previous row
  • Tabulation Approach: Build the triangle bottom-up, storing each row as we go
  • Memoization: The triangle itself stores all computed values for later use

Step-by-step execution for numRows = 5:

Row 0: [1]                           (base case)

Row 1: [1, 1]                        (edges are 1)

Row 2: [1, 2, 1]
       Interior: prevRow[0] + prevRow[1] = 1 + 1 = 2

Row 3: [1, 3, 3, 1]
       Interior[0]: prevRow[0] + prevRow[1] = 1 + 2 = 3
       Interior[1]: prevRow[1] + prevRow[2] = 2 + 1 = 3

Row 4: [1, 4, 6, 4, 1]
       Interior[0]: prevRow[0] + prevRow[1] = 1 + 3 = 4
       Interior[1]: prevRow[1] + prevRow[2] = 3 + 3 = 6
       Interior[2]: prevRow[2] + prevRow[3] = 3 + 1 = 4

Key Insight: This is tabulation DP because we solve smaller subproblems (earlier rows) first and build up to the final result, storing all intermediate results.

14.13.5.2 Analysis

  • Time Complexity: \(O(n^2)\)
    • Outer loop: \(n\) rows
    • Inner loop: Row \(i\) has \(i\) elements
    • Total elements: \(1 + 2 + 3 + ... + n = \frac{n(n+1)}{2} = O(n^2)\)
    • Each element is computed in constant time (one addition)
    • This is optimal since the output size itself is \(O(n^2)\)
  • Space Complexity: \(O(n^2)\) for the output triangle
    • Row \(i\) contains \(i+1\) elements
    • Total space: \(\sum_{i=0}^{n-1}(i+1) = \frac{n(n+1)}{2} = O(n^2)\)
    • This is inherent to the problem—we must store all values
    • Auxiliary space: \(O(1)\) (only loop variables and temporary references)

Why This Approach is Optimal:

  • We must generate all \(O(n^2)\) elements—no way to avoid this
  • Each element requires at most 2 additions from the previous row
  • We cannot do better than \(O(n^2)\) time and space for this problem

14.13.5.3 Implementation Steps

Initialization: 1. Create empty result list triangle 2. Handle base case: if numRows == 0, return empty triangle 3. Add first row: [1] (base case of DP)

DP Table Construction (Bottom-Up): 4. For each row index row from 1 to numRows - 1: 1. Retrieve previous row: prevRow = triangle.get(row - 1) 2. Create new row list: current = new ArrayList<>() 3. Add first element: current.add(1) (boundary condition) 4. DP Transition: For each interior position j from 1 to row - 1: - Compute from previous row: current.add(prevRow.get(j-1) + prevRow.get(j)) - This is the DP recurrence relation in action 5. Add last element: current.add(1) (boundary condition) 6. Store computed row: triangle.add(current) (memoization)

Return Result: 5. Return triangle (contains all \(n\) rows)

14.13.5.4 Code - Java

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> triangle = new ArrayList<>();

    if (numRows == 0) {
        return triangle;
    }

    // Base case: first row is [1]
    triangle.add(Collections.singletonList(1));

    // Build each subsequent row from the previous row (tabulation DP)
    for (int row = 1; row < numRows; row++) {
        List<Integer> prevRow = triangle.get(row - 1);
        List<Integer> current = new ArrayList<>();

        // First element is always 1
        current.add(1);

        // DP recurrence: interior elements are sum of two elements above
        for (int j = 1; j < row; j++) {
            current.add(prevRow.get(j - 1) + prevRow.get(j));
        }

        // Last element is always 1
        current.add(1);

        // Store computed row (memoization)
        triangle.add(current);
    }

    return triangle;
}

DP Pattern Identification: - State: triangle[i] represents the \(i\)-th row of Pascal’s Triangle - Base Case: triangle[0] = [1] - Transition: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] - Order: Bottom-up (compute row 0, then 1, then 2, etc.) - Type: Tabulation (iterative, not recursive)

This is a classic example of tabulation DP where each subproblem (row) depends only on the immediately previous subproblem (previous row), resulting in a clean iterative solution with optimal complexity.