Skip to main content

16. Pascal's Triangle

easyAsked at Reddit

Generate the first numRows of Pascal's Triangle. Reddit asks this to gauge basic 2D-array fluency — the same iteration pattern they use to build precomputed lookup tables for vote-decay coefficients.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, warm-up question.

Problem

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.

Constraints

  • 1 <= numRows <= 30

Examples

Example 1

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

Example 2

Input
numRows = 1
Output
[[1]]

Approaches

1. Combinatorial formula per cell

Compute C(n, k) = n! / (k! (n-k)!) for each cell.

Time
O(n^3)
Space
O(n^2)
function generate(numRows) {
  const fact = (n) => { let r = 1; for (let i = 2; i <= n; i++) r *= i; return r; };
  const out = [];
  for (let i = 0; i < numRows; i++) {
    const row = [];
    for (let k = 0; k <= i; k++) row.push(fact(i) / (fact(k) * fact(i - k)));
    out.push(row);
  }
  return out;
}

Tradeoff: Recomputes factorials. Anti-pattern when DP gives O(n^2).

2. Row-by-row DP (optimal)

Each row starts and ends with 1. Middle cells = prevRow[j-1] + prevRow[j].

Time
O(n^2)
Space
O(n^2)
function generate(numRows) {
  const out = [];
  for (let i = 0; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) {
      row[j] = out[i - 1][j - 1] + out[i - 1][j];
    }
    out.push(row);
  }
  return out;
}

Tradeoff: Builds each row from the previous. Classic DP — same shape as Reddit's vote-decay lookup table.

Reddit-specific tips

Reddit interviewers want clear off-by-one handling: row i has i+1 elements; only middle indices (1 .. i-1) need the sum. Bonus signal: mention that this DP is precisely how they'd precompute binomial coefficients for hot-score percentile calculations.

Common mistakes

  • Allocating new Array(i) instead of new Array(i + 1).
  • Looping 0 to i and overwriting the 1s.
  • Computing factorials repeatedly when DP is asked for.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Pascal's triangle II (LC 119) — O(k) space for a single row.
  • Counting paths in a grid (LC 62) — same recurrence.
  • Probability problems using binomial coefficients.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Could we generate row k in O(k) space?

Yes — see LC 119. Iterate from right to left to avoid clobbering values you still need.

What's the closed-form value?

row[i][k] = C(i, k). For numRows up to 30, factorial fits in a 64-bit float — but bigger N requires BigInt.

Practice these live with InterviewChamp.AI

Drill Pascal's Triangle and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →