Pascal Triangle Dry Run Explained | Running Product Approach

Three ways to solve the classic Pascal's Triangle interview question — with intuition, C++ code, an animated dry run for each approach, and complexity analysis you can actually explain in an interview.

On this page

Problem statement
Approach 1 — Brute force (factorial formula)
Approach 2 — Better (Pascal's Rule)
Approach 3 — Optimal (multiplicative formula)
Complexity comparison
Interview notes
FAQ

Problem Statement

Given an integer numRows, generate the first numRows rows of Pascal's Triangle.

In Pascal's Triangle, each number is the sum of the two numbers directly above it. Row indices and column indices are 0-based. Row i has exactly i + 1 elements, and the first and last element of every row is always 1.

Example: For numRows = 5, the output is:

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

To keep every approach grounded in the same example, we'll trace how each one computes row 4, column 2 → the value 6 — once by direct combinatorics, once by summing parents, and once by a running product.

Approach 1 · Brute Force

Compute Every Cell with the Factorial Formula

Intuition

Every entry in Pascal's Triangle is a binomial coefficient: the value at row n, column r equals C(n, r) — "n choose r" — the number of ways to choose r items from n. The most direct way to compute this is the textbook formula:

C(n, r) = n! / (r! × (n - r)!)

So the brute-force plan is simple: for every cell in every row, compute this formula from scratch using its own fresh factorial calculations. It's the first thing most people write down because it comes straight from the math definition — but it repeats a huge amount of work and factorials overflow fast.

Algorithm

Write a helper factorial(n) that multiplies 1 × 2 × ... × n.
Write nCr(n, r) that returns factorial(n) / (factorial(r) * factorial(n - r)).
Loop i from 0 to numRows - 1 (the row).
For each row, loop j from 0 to i (the column) and set triangle[i][j] = nCr(i, j).

c++ code:

long long factorial(int n) {
    long long f = 1;
    for (int i = 2; i <= n; i++) f *= i;
    return f;
}

long long nCr(int n, int r) {
    return factorial(n) / (factorial(r) * factorial(n - r));
}

vector<vector<long long>> generate(int numRows) {
    vector<vector<long long>> triangle(numRows);
    for (int i = 0; i < numRows; i++) {
        triangle[i].resize(i + 1);
        for (int j = 0; j <= i; j++) {
            triangle[i][j] = nCr(i, j);
        }
    }
    return triangle;
}

Dry Run

Complexity Analysis

Metric	Value	Why
Time	O(n³)	~n² cells, each cell recomputes factorials in O(n) time
Space	O(1) extra	Only the output triangle is stored, no auxiliary structures
Practical issue	Overflow	factorial(n) blows past long long range quickly

Approach 2 · Better

Build Each Row from the Previous Row (Pascal's Rule)

Intuition

Instead of recomputing a binomial coefficient from raw factorials, use the defining recurrence of Pascal's Triangle directly: every interior cell is the sum of the two cells above it.

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

This turns the problem into simple dynamic programming: once row i-1 exists, row i can be built with only additions — no factorials, no overflow risk from multiplying large numbers, and no repeated work across cells.

Algorithm

Set the first and last element of every row to 1 (the boundary of the triangle).
For each row i, loop columns j from 1 to i - 1.
Set triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j].
Move to the next row, reusing the row you just finished

C++ CODE

vector<vector<long long>> generate(int numRows) {
    vector<vector<long long>> triangle(numRows);
    for (int i = 0; i < numRows; i++) {
        triangle[i].resize(i + 1);
        triangle[i][0] = triangle[i][i] = 1;
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    return triangle;
}

DRY RUN

Complexity analysis

Metric	Value	Why
Time	O(n²)	Every cell is computed exactly once with a single addition
Space	O(n²)	The full triangle must be stored to answer the problem — this equals the output size
Improvement	No overflow risk from factorials	Values grow only through addition, matching the true output magnitude

Approach 3 · Optimal

Generate Any Row Directly with a Running Product

Intuition

Pascal's Rule is already efficient, but it forces you to build every earlier row just to get one row. If an interviewer follows up with "what if you only need row n, not the whole triangle?" — you need a formula that walks across one row without depending on the row above it.

The trick: consecutive binomial coefficients in the same row are related by a simple ratio, so each value can be derived from the previous one using only one multiplication and one division:

row[j] = row[j-1] × (n - j + 1) / j, starting from row[0] = 1

Algorithm

Start each row with row[0] = 1.
For j from 1 to n, compute row[j] = row[j-1] * (n - j + 1) / j.
Repeat for each row n from 0 to numRows - 1 if you need the full triangle — or run it once for a single target row.

C++ CODE

vector<long long> generateRow(int n) {
    vector<long long> row(n + 1);
    row[0] = 1;
    for (int j = 1; j <= n; j++) {
        row[j] = row[j - 1] * (n - j + 1) / j;
    }
    return row;
}

vector<vector<long long>> generate(int numRows) {
    vector<vector<long long>> triangle(numRows);
    for (int i = 0; i < numRows; i++) {
        triangle[i] = generateRow(i);
    }
    return triangle;
}

Dry Run

Complexity analysis

Metric	Value	Why
Time	O(n²) for full triangle, O(r) for a single row	Each element still takes O(1) work, but you can stop after any row
Space	O(1) extra per row	Only the previous value is needed, not a stored row above
Why optimal	No factorial overflow, no dependency on prior rows	Ideal when only one row or one cell is needed

Interview Notes

How to talk through it

Start by naming the recurrence out loud: "each cell is the sum of the two above it." This signals you recognize the DP structure immediately.
Mention the brute-force factorial approach briefly to show you know the combinatorics connection, then pivot to why it's inefficient — interviewers want to see you reject it for a reason, not just because you were told to.
If asked to optimize space, bring up generating rows in-place from right to left using a 1D array, so you don't need a full 2D structure when only the last row matters.

Common follow-ups

"Get only row k" (Pascal's Triangle II) → use the running-product formula directly, O(k) time, O(1) extra space.
"Get element at (row, col)" → same running-product formula, walk only up to col.
"What if numRows is large, like 10⁵?" → discuss modular arithmetic (values mod a prime) since raw binomial coefficients grow astronomically large.
"Can you do it recursively?" → yes, but flag that naive recursion without memoization re-derives the same sub-values repeatedly, similar to the brute-force issue.

Edge cases to mention

numRows = 0 → return an empty result.
numRows = 1 → return just [[1]].
Large row indices where long long can still overflow — worth flagging even in the optimal approach.

Frequently Asked Questions

What is Pascal's Triangle and why is it asked in interviews?

It's a triangular array where each number is the sum of the two numbers directly above it. Interviewers use it to test whether you can spot a recurrence relation and reason clearly about time and space tradeoffs between three genuinely different valid solutions.

Which approach should I lead with in an interview?

Name the brute-force factorial idea quickly to show you understand the math, but write and explain the Pascal's Rule (better) approach as your main solution, then mention the running-product (optimal) version as a strong follow-up if asked to reduce space or handle a single row.

Why does the brute-force factorial method overflow so easily?

It computes full factorials like n! directly, which grows far faster than the actual binomial coefficient it's trying to produce, so it exhausts the range of a 64-bit integer long before the final answer would.

video reference:

problem link:

https://leetcode.com/problems/pascals-triangle/description/

Problem Statement

Approach 1 · Brute Force

Compute Every Cell with the Factorial Formula

Intuition

Algorithm

c++ code:

Dry Run

Complexity Analysis

Approach 2 · Better

Build Each Row from the Previous Row (Pascal's Rule)

Intuition

Algorithm

C++ CODE

DRY RUN

Complexity analysis

Approach 3 · Optimal

Generate Any Row Directly with a Running Product

Intuition

Algorithm

C++ CODE

Dry Run

Complexity analysis

Interview Notes

How to talk through it

Common follow-ups

Edge cases to mention

Related problems

Frequently Asked Questions

chakradhar

Problem Statement

Approach 1 · Brute Force

Compute Every Cell with the Factorial Formula

Intuition

Algorithm

c++ code:

Dry Run

Complexity Analysis

Approach 2 · Better

Build Each Row from the Previous Row (Pascal's Rule)

Intuition

Algorithm

C++ CODE

DRY RUN

Complexity analysis

Approach 3 · Optimal

Generate Any Row Directly with a Running Product

Intuition

Algorithm

C++ CODE

Dry Run

Complexity analysis

Interview Notes

How to talk through it

Common follow-ups

Edge cases to mention

Related problems

Frequently Asked Questions