Pascal’s Triangle (LeetCode #118) – Explained Step by Step. Pascal’s Triangle is one of those problems that looks simple but hides powerful mathematical patterns. It’s a favorite on LeetCode (Problem #118), and a must-practice for interviews.

Pascal’s Triangle is a triangular array of integers where each number is the sum of the two numbers directly above it. It shows up everywhere: binomial expansions, combinatorics, dynamic programming, and even probability.

Given an integer numRows, our goal is to return the first numRows of Pascal’s Triangle.

What You’ll Build

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

Input: numRows = 1
Output: [[1]]

Core Idea (Dynamic Construction)

1. The first row is always [1].
2. Each row:
   • Starts and ends with 1.
   • Every middle element is the sum of the two numbers above it from the previous row.

Mathematically, for row i (0-indexed) and position j (1 ≤ j < i):
row[i][j] = row[i-1][j-1] + row[i-1][j]

Clean Python Solution (with rich inline comments)

def generate(numRows: int):
    # 'triangle' will store all the rows we build, e.g., [[1], [1,1], [1,2,1], ...]
    triangle = []

    # Build rows one by one, from 0 to numRows-1
    for i in range(numRows):
        # Start a new row with length (i + 1), prefilled with 1s
        # Example: i=0 -> [1], i=1 -> [1,1], i=2 -> [1,1,1], ...
        row = [1] * (i + 1)

        # Fill the "middle" of the row (indexes 1..i-1) using previous row sums.
        # We skip j=0 and j=i because they must remain 1.
        for j in range(1, i):
            # Each middle element is the sum of the two numbers above it
            # from the previous row: triangle[i-1][j-1] and triangle[i-1][j]
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]

        # Add the completed row to our triangle
        triangle.append(row)

    # Return the full triangle of 'numRows' rows
    return triangle

Line-by-Line Walkthrough

• triangle = []
  Prepare an empty list to collect all rows. After we’re done, this will be our answer.
• for i in range(numRows):
  Build each row iteratively. i is the 0-based row index; total rows to create is numRows.
• row = [1] * (i + 1)
  Every row starts (and ends) with 1. Pre-filling all positions with 1 cleverly handles edges.
• for j in range(1, i):
  Only middle values need computation. For i < 2, this loop doesn’t run (no middle elements).
• row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
  Pascal’s rule: current value is the sum of the two numbers above it in the previous row.
• triangle.append(row)
  Push the completed row into our result.
• return triangle
  Done—return the first numRows of Pascal’s Triangle.

Dry Run (numRows = 5)

• i = 0: row = [1] → triangle = [[1]]
• i = 1: row = [1, 1] → triangle = [[1],[1,1]]
• i = 2: start [1,1,1] → middle: row[1] = 1+1 = 2 → [1,2,1]
• i = 3: start [1,1,1,1] → row[1]=1+2=3, row[2]=2+1=3 → [1,3,3,1]
• i = 4: start [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]

Final: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Complexity

• Time: O(n2)O(n^2)
• Space: O(n2)O(n^2) — we store all rows up to length n.

Edge Cases

• numRows = 1 → [[1]] (middle loop never runs).
• numRows = 2 → [[1],[1,1]].
• Upper bound numRows = 30 is small; the O(n2)O(n^2) approach is perfectly fine.

Alternative Approaches

1) Using Binomial Coefficients (Combinatorics)

Each element is (ij)\binom{i}{j} (i choose j). Python has a built-in:

import math

def generate_combinatorial(numRows: int):
    triangle = []
    for i in range(numRows):
        row = [math.comb(i, j) for j in range(i + 1)]
        triangle.append(row)
    return triangle

Pros: Very concise.
Cons: Less “DP” flavor; some interviewers prefer the incremental build.

2) Memory-Lean Row-by-Row (If you only need to print rows)

You can generate and print each row without keeping the whole triangle, but since the problem asks to return all rows, the standard solution above is the right fit.

JavaScript Version (for Web Projects)

function generate(numRows) {
  const triangle = [];

  for (let i = 0; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) {
      row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
    }
    triangle.push(row);
  }

  return triangle;
}

Common Pitfalls (and Fixes)

• Off-by-one in the inner loop:
  Use for j in range(1, i) (Python) or for (let j = 1; j < i; j++) (JS). Don’t touch j=0 or j=i.
• Forgetting to prefill with 1s:
  Edges must stay 1. Prefill with [1] * (i + 1) or Array(i+1).fill(1) and then fill only the middle.
• Modifying previous rows:
  Only read from triangle[i-1]. Write to the new row.

Quick Tests

assert generate(1) == [[1]]
assert generate(2) == [[1],[1,1]]
assert generate(5) == [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
print("All tests passed!")

Wrap-Up (Connect Kreations POV)

This problem is a great introduction to dynamic programming and combinatorics. The iterative build mirrors many real-world patterns: initialize safe edges, then compute dependable middles. If you’re teaching or learning with Connect Kreations, try both the DP and math.comb variants to see how different mindsets approach the same problem.