15. Pascal's Triangle

easyAsked at DigitalOcean

Generate the first numRows of Pascal's triangle — tests iterative DP thinking and clean 2D array construction.

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

Problem

Given an integer numRows, return the first numRows of Pascal's triangle. In Pascal's triangle, 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. Brute force (nested loops without reuse)

Compute each element as C(row, col) from scratch using the binomial formula — correct but wasteful.

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

// compute C(n,k) naively each time
function generate(numRows) {
  const result = [];
  for (let i = 0; i < numRows; i++) {
    const row = [];
    for (let j = 0; j <= i; j++) {
      row.push(comb(i, j));
    }
    result.push(row);
  }
  return result;
}

Tradeoff:

2. Iterative DP row-by-row

Build each row from the previous row: edges are always 1, interior values are prevRow[j-1] + prevRow[j]. O(n^2) time and space but with minimal constant factor.

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

function generate(numRows) {
  const result = [[1]];
  for (let i = 1; i < numRows; i++) {
    const prev = result[i - 1];
    const row = [1];
    for (let j = 1; j < i; j++) {
      row.push(prev[j - 1] + prev[j]);
    }
    row.push(1);
    result.push(row);
  }
  return result;
}

Tradeoff:

DigitalOcean-specific tips

DigitalOcean appreciates candidates who mention that the same DP pattern applies to combinatorial counting in network path analysis and provisioning cost tables.

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

Practice these live with InterviewChamp.AI →