Skip to main content

15. Pascal's Triangle

easyAsked at Instacart

Generate the first N rows of Pascal's triangle — Instacart uses this for array-iteration warmups before promo-tier breakdown problems.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer numRows, return the first numRows of Pascal's triangle, where 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. Math.comb formula

Compute each entry via binomial coefficient nCk.

Time
O(n^2)
Space
O(n^2)
function comb(n, k) {
  let r = 1n;
  for (let i = 0; i < k; i++) r = r * BigInt(n - i) / BigInt(i + 1);
  return Number(r);
}

Tradeoff:

2. Row-by-row accumulator

Each new row is built from the previous row by summing neighbor pairs.

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

Tradeoff:

Instacart-specific tips

Instacart loves the in-place row construction — they'll ask how you'd memoize this for repeated coupon-stack lookups.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Instacart coding interview questions

See all Instacart problems →

Companies that also ask Pascal's Triangle