15. Pascal's Triangle

easyAsked at Lyft

Generate the first numRows of Pascal's triangle.

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

Problem

Given an integer numRows, return the first numRows of Pascal's triangle. Each row is constructed from the row above by summing adjacent pairs.

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

Compute each cell via C(n, k) using factorials.

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

function C(n,k){let r=1; for (let i=1;i<=k;i++) r=r*(n-i+1)/i; return Math.round(r);}
const out=[]; for (let i=0;i<numRows;i++){const row=[]; for (let j=0;j<=i;j++) row.push(C(i,j)); out.push(row);}

Tradeoff:

2. Incremental rows

Build each row from the previous one — first and last entries are 1, middle is the sum of two parents.

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:

Lyft-specific tips

Lyft will probe whether you can derive the row formula from the previous row — they like candidates who avoid factorial overflow by using DP build-up.

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 Lyft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →