You're handed a single integer rowIndex. Return exactly that row of Pascal's triangle — using 0-indexed counting, so rowIndex = 0 is the very top [1].
In Pascal's triangle, every number is the sum of the two numbers directly above it. The edges are always 1, and each interior value grows from the pair sitting on its shoulders:
row 0: 1
row 1: 1 1
row 2: 1 2 1
row 3: 1 3 3 1
row 4: 1 4 6 4 1
Return the row as a flat list of integers, left to right.
Input: rowIndex = 3 Output: [1,3,3,1] The 4th row (0-indexed) reads 1, 3, 3, 1 — the middle 3s are 1+2 and 2+1 from row 2.
Input: rowIndex = 0 Output: [1] The very top of the triangle.
Input: rowIndex = 1 Output: [1,1] Two edges, no interior.
- 0 <= rowIndex <= 33
Pascal's Triangle II turns the space screw: you need only one row, so storing the whole triangle is wasteful. The fix is a rolling in-place array updated right-to-left — the exact same space-saving move that powers the 0/1 knapsack and coin-change DP. The direction of the sweep is, once again, the whole trick.
n is C(n,0), C(n,1), ..., C(n,n), so it can be generated on its own without the rows above.Given rowIndex (0-indexed), return exactly that row of Pascal's triangle as a flat list.
Worked example — rowIndex = 3, rolling [1,1,1,1] right-to-left
gen for row 1: row[1] += row[0] → [1, 1, 1, 1] (edges stay 1) gen for row 2: row[2]+=row[1]; row[1]+=row[0] → [1, 2, 1, 1] gen for row 3: row[3]+=row[2]; row[2]+=row[1]; row[1]+=row[0] → [1, 3, 3, 1] ✓
“Is rowIndex 0-indexed?”
Yes — rowIndex = 0 is [1], rowIndex = 3 is [1,3,3,1].
“Do I return only that one row?”
Yes — not the whole triangle, which is exactly what lets you save space.
“What about rowIndex = 0 or 1?”
[1] and [1,1] — pure edges, no interior updates.
“Could the values overflow?”
For rowIndex <= 33 the largest entry fits in 64-bit; the additive roll never multiplies, so it stays exact.
“A flat list of integers?”
Yes, left to right.
“What extra space is expected?”
O(rowIndex) — a single array (the answer itself), with no triangle stored above it.
A couple of questions.
rowIndex is 0-indexed, and I return just that single row?
Is O(rowIndex) extra space the target?
Then I'll roll one array in place, updating right-to-left so I read old values before overwriting.
Every row above is scaffolding you throw away. Keeping just one array and evolving it row by row drops the space from O(rowIndex²) to O(rowIndex) — the array is the answer.
Starting from all 1s, advancing one generation adds each slot's left neighbour into it: row[j] += row[j-1]. Repeat rowIndex times and the array holds the requested row. The edges never change because row[0] stays 1.
row[j] needs the old row[j-1]. If you sweep left-to-right, row[j-1] was already updated this generation and you feed the new value forward — corrupting everything downstream. Sweeping right-to-left keeps each left neighbour pristine until it's read.
| Build whole triangle | One rolling row | |
|---|---|---|
| Idea | Generate every row, return the last | Evolve a single array in place |
| Time | O(rowIndex²) | O(rowIndex²) |
| Space | O(rowIndex²) | O(rowIndex) |
The full code for both is in the Approaches selector below.
Key takeaway
When you need only one row of a DP that's normally built as a 2-D table, roll a single array in place — here row[j] += row[j-1] for rowIndex generations, swept right-to-left so each slot reads its left neighbour's old value first. O(rowIndex) space; the same trick space-optimizes 0/1 knapsack and coin change.