15. Pascal's Triangle

easyAsked at Booking

Generate the first n rows of Pascal's Triangle — Booking screens this for clean iterative-DP wiring before moving to availability-grid DP.

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 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. Combinatoric formula

Compute each cell with C(n,k) — overflow risk and recompute.

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

const fact=n=>{let r=1; for(let i=2;i<=n;i++) r*=i; return r;};
const C=(n,k)=>fact(n)/(fact(k)*fact(n-k));

Tradeoff:

2. Iterative row build

Each new row is built by summing adjacent values of the previous row.

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

function generate(numRows) {
  const tri = [];
  for (let i = 0; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) row[j] = tri[i-1][j-1] + tri[i-1][j];
    tri.push(row);
  }
  return tri;
}

Tradeoff:

Booking-specific tips

Booking grades for in-place row-building intuition — call out the parallel with computing nightly cumulative-price ladders row-by-row.

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

Practice these live with InterviewChamp.AI →