Skip to main content

16. Pascal's Triangle

easyAsked at Datadog

Generate the first N rows of Pascal's triangle. Datadog uses this as a simple DP warmup — each row depends only on the previous, the same shape as rolling-window aggregates over consecutive minutes.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Mentioned occasionally as a Datadog phone-screen warmup.

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. Combinatorial formula per cell

For each (i, j), compute C(i, j) directly via factorial.

Time
O(n^3)
Space
O(n^2)
function generate(numRows) {
  function fact(k) { let p = 1n; for (let i = 2n; i <= BigInt(k); i++) p *= i; return p; }
  const out = [];
  for (let i = 0; i < numRows; i++) {
    const row = [];
    for (let j = 0; j <= i; j++) row.push(Number(fact(i) / (fact(j) * fact(i - j))));
    out.push(row);
  }
  return out;
}

Tradeoff: Cube time. BigInt avoids overflow but is slow. Datadog will fail this for ignoring the recurrence.

2. Iterative row-by-row (optimal)

Each row starts and ends with 1; interior cells are sums of pairs from the previous row.

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

Tradeoff: Quadratic time, mandatory because the OUTPUT is quadratic. O(1) extra space beyond the output.

Datadog-specific tips

Datadog grades on whether you spot that each row depends only on the previous. They'll follow up with: 'Now compute only the Kth row in O(K) space.' Show that you can roll a single row in place by iterating right-to-left.

Common mistakes

  • Allocating each row dynamically with push — fine for JS but inefficient in other languages.
  • Off-by-one in the inner loop — last row has i+1 entries, easy to miss.
  • Trying to use BigInt for n <= 30 — unnecessary overhead.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Pascal's Triangle II (LC 119) — return only the kth row in O(k) space.
  • Combinations C(n, k) — direct application.
  • Triangle (LC 120) — minimum path sum down a triangle.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why not the formula?

It's correct but quadratic for the output AND ignores the recurrence the interviewer wants to see. Datadog grades on pattern recognition.

Can you do it in O(k) space for one row?

Yes — see the follow-up. Iterate the row in place from right to left so you don't clobber values you still need to read.

Practice these live with InterviewChamp.AI

Drill Pascal's Triangle and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →