Pascal's Triangle

Given an integer numRows, build the first numRows rows of Pascal's triangle and return them.

Pascal's triangle starts with a single 1 at the top. Every entry below is the sum of the two entries directly above it; where there is only one entry above (the left and right edges), the value is always 1.

Return the triangle as a list of rows, where row i (0-indexed) contains i + 1 numbers.

Hints

· Stuck? Reveal one nudge at a time.

You're not asked for a single value — you must output the whole triangle, row by row. How does a brand-new row relate to the row right before it?

The first and last entry of every row are always 1. Only the interior entries need work — and each of those is a sum of two neighbours one row up.

Set row[j] = prev[j-1] + prev[j]. Or, if you know combinatorics, row i entry k is C(i, k), which you can scale from its left neighbour with (i-k+1)/k.

Common doubts

Those edge cells have only one cell above them (there's no second parent off the side), so they inherit that single 1 straight down from the apex.

The judge normalises each row (sorts it) and then sorts the rows, so any correct triangle passes regardless of internal ordering. Focus on producing the right values.

For numRows <= 30 the largest value is C(29, 14) = 67863915, well within a 32-bit int. The multiplicative method multiplies before dividing, so intermediate products stay small too.

Interview follow-ups

· What an interviewer asks next.

Yes — that's the "single row in O(k) space" variant. Keep one array and update it in place from right to left, or use the C(k, j) scaling trick to emit one row without building the others.

The output itself is O(n²), so that cost is unavoidable, but you can stream rows one at a time and, if only specific entries are needed, compute them modulo a prime using precomputed factorials.

Fun facts

The diagonals of Pascal's triangle hide famous sequences: the third diagonal is the triangular numbers 1, 3, 6, 10…, and the shallow diagonals sum to the Fibonacci numbers.
Colour every odd entry and the Sierpiński triangle appears — the same fractal shows up in cellular automata and the Chaos Game.

Asked at

AmazonMicrosoftGoogleAdobe

Frequently Sometimes Occasionally

Example 1

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Each interior number is the sum of the two above it: 2 = 1+1, 3 = 1+2, 6 = 3+3.

Example 2

Input: numRows = 1
Output: [[1]]
Just the apex of the triangle.

Constraints

- 1 <= numRows <= 30

Pascal's Triangle is a lesson in recognizing when you're already at the optimal complexity. The answer is O(n²) numbers, so no algorithm can be faster than O(n²) — the only thing left to optimize is how much you carry between rows. The classic build sums the two entries above each cell; the slicker build treats each row as binomial coefficients.

Prerequisites

Before you start

· Concepts used directly in the solution.

Row-from-previous-row. Each row is built by summing adjacent pairs of the row above, with 1s on the edges.

Binomial coefficients. Entry k of row i is C(i, k) — the same numbers that expand (a+b)^i. This lets you skip storing the previous row.

Output-bound complexity. When the answer itself has O(n²) entries, O(n²) work is optimal — you can't emit fewer numbers than the answer contains.

Understand the problem

Given numRows, return the first numRows rows of Pascal's triangle. Row i (0-indexed) has i+1 entries; the first and last are always 1.

Worked example — numRows = 5

  row 0:        1
  row 1:       1 1
  row 2:      1 2 1          2 = 1+1
  row 3:     1 3 3 1         3 = 1+2
  row 4:    1 4 6 4 1        6 = 3+3

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are rows 0-indexed, and how many entries does row i have?”

0-indexed; row i has i+1 entries. Confirms the shape of the output.

“Can numRows be 1?”

Yes — just the apex [[1]].

Edge cases

“Could the values overflow?”

For numRows <= 30 the largest entry is C(29,14) ≈ 6.8×10⁷, safe in 32-bit. The multiplicative build multiplies before dividing to keep intermediates small.

Output format

“Return the full triangle as a list of rows?”

Yes — a jagged list where each row is its own list.

Constraints & scale

“How big can numRows be?”

Up to 30. The output has O(numRows²) entries, so O(numRows²) time is unavoidable and perfectly fine here.

The ideal opening — say it like this

A couple of quick questions.

Rows are 0-indexed, and row i has i+1 entries?

I return the whole triangle as a list of rows?

Since the output itself is O(n²), I'll build it row by row from the one above.

Key observations

1Aha

Each entry is the sum of its two parents

Interior entry row[j] = prev[j-1] + prev[j], and the edges (j = 0 or j = i) are always 1. That single rule builds every row from the one above — the most direct way to generate the triangle.

2Aha

O(n²) is optimal because the answer is O(n²)

There are 1 + 2 + ... + numRows entries to produce. You cannot output them in fewer steps than there are numbers, so O(numRows²) is a lower bound — the goal isn't a faster asymptotic, just less carried state.

3Aha

A row is binomial coefficients — scale one running value

Entry k of row i is C(i, k). Stepping across a row, C(i, k) = C(i, k-1) × (i - k + 1) / k. So you can emit a whole row by scaling a single running number left to right — no need to remember the previous row at all.

Brute force vs optimal

	Sum from above	Binomial scan
Idea	row[j] = prev[j-1] + prev[j]	Scale C(i,k-1) → C(i,k) across the row
Time	O(n²)	O(n²)
Needs previous row

The full code for both is in the Approaches selector below.

Summary

Key takeaway

Pascal's triangle is output-bound at O(n²), so the win is in carried state, not speed. Build each row from the previous by summing adjacent pairs — or recognise each row as binomial coefficients C(i,k) and scale one running value across it (multiplying before dividing) to avoid storing the prior row entirely.