Skip to main content

11. Pascal's Triangle

easyAsked at Notion

Generate the first numRows of Pascal's triangle. Notion uses this as a row-building warmup before harder DP grid problems.

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

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion uses this as a DP warmup.
  • LeetCode Discuss (2025)— Phone screen warmup.

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

Each cell triangle[i][j] = C(i,j). Compute factorials.

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

Tradeoff: Risk of overflow for big n; floating-point errors. The DP build is preferred.

2. Row-by-row from previous (optimal)

Each new row's value at j is prev[j-1] + prev[j]. Edge values are 1.

Time
O(n^2)
Space
O(n^2) output
function generate(numRows) {
  const res = [[1]];
  for (let i = 1; i < numRows; i++) {
    const prev = res[i-1];
    const row = [1];
    for (let j = 1; j < i; j++) row.push(prev[j-1] + prev[j]);
    row.push(1);
    res.push(row);
  }
  return res;
}

Tradeoff: Simple DP. Integer arithmetic, no overflow risk for n<=30.

Notion-specific tips

Notion uses this as a quick comfort check with 2D array index arithmetic. Mention up front that row i has i+1 elements and the edges are always 1.

Common mistakes

  • Indexing prev[j] when j is out of bounds at edges — write edges as constants 1.
  • Off-by-one between numRows count and zero-indexed row index.
  • Allocating with new Array(i).fill(1) and then forgetting to update interior.

Follow-up questions

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

  • Pascal's Triangle II (LC 119) — return just row k with O(k) space.
  • Compute C(n,k) mod p efficiently (Lucas's theorem).
  • Visualize triangle for arbitrary n.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Can I use O(k) space for row k?

Yes — iterate j from right to left so you don't overwrite values you still need. That's LC 119.

Why prev[j-1] + prev[j]?

Pascal's identity: C(n,k) = C(n-1,k-1) + C(n-1,k). It's literally the rule.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →