15. Pascal's Triangle

easyAsked at Dropbox

Generate the first numRows of Pascal's Triangle; Dropbox uses it as a primer for building up tabulated state, a pattern that recurs in their hash-tree calculations.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Given an integer numRows, return the first numRows of Pascal's Triangle, where each number is the sum of the two 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. Binomial formula

Use n choose k for each entry.

Time: O(n^3)
Space: O(n^2)

const C=(n,k)=>{let r=1;for(let i=0;i<k;i++)r=r*(n-i)/(i+1);return r};
return Array.from({length:numRows},(_,n)=>Array.from({length:n+1},(_,k)=>C(n,k)));

Tradeoff:

2. Row-by-row build

Each row starts and ends with 1; interior cell i is prev[i-1]+prev[i]. No re-computation.

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:

Dropbox-specific tips

Dropbox interviewers like the in-place fill (preallocate row of 1s, only fill interior) — it shows you're thinking about cache locality the way their chunk-storage layer does.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →