Pascal's Triangle II
Easy · Arrays & Hashing · Array · Dynamic Programming · Math
Problem
In Pascal's triangle every row begins and ends with 1, and every other number is the sum of the two numbers directly above it. Rows are numbered from 0: row 0 is [1], row 1 is [1, 1], row 2 is [1, 2, 1].
Given rowIndex, return that one row of the triangle.
Aim for O(rowIndex) extra space: you do not need the rows above it once you have used them.
Examples
Input: rowIndex = 4 Output: [1,4,6,4,1]
Row 4 holds C(4, 0) to C(4, 4): 1, 4, 6, 4, 1.
Input: rowIndex = 0 Output: [1]
Row 0 is the single 1 at the top.
Input: rowIndex = 2 Output: [1,2,1]
The middle entry is 1 + 1 = 2.
Constraints
- 0 <= rowIndex <= 33
Approaches
- One row, updated in place from right to left — time O(k²), space O(k)
Follow-up
Every entry of the row is at most C(33, 16) = 1,166,803,110, which fits a 32-bit integer, but the product C(n, j) · (n − j) in the formula does not. Past row 33 the entries themselves outgrow 32 bits, and past row 67 they outgrow 64 bits: then you need big integers, or the row modulo a prime.
Related problems
Start free on Cariara · Coding problems · System design studio
