Skip to main content

16. Pascal's Triangle

easyAsked at Spotify

Generate the first numRows of Pascal's Triangle.

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

Problem

Given an integer numRows, return the first numRows of Pascal's Triangle. Each row is built from the row above by summing adjacent entries.

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

Use C(n,k) = n!/(k!(n-k)!) for each cell

Time
O(n^2)
Space
O(n^2)
// Build each row by computing each binomial; overflow risk for big rows, slower than row-by-row.

Tradeoff:

2. Row-by-row build

Each row uses only the previous row. Sum adjacent pairs and bookend with ones.

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

Tradeoff:

Spotify-specific tips

Spotify rarely cares about Pascal's Triangle in prod, so the bonus signal is talking through the reuse-previous-row pattern and how it foreshadows DP over precomputed state.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Spotify coding interview questions

See all Spotify problems →

Companies that also ask Pascal's Triangle