119. Pascal's Triangle II
Same triangle as Pascal's Triangle, different ask: instead of the whole thing, your function receives an integer rowIndex and returns just that one row, as a list of integers. Rows are numbered from zero, so rowIndex = 0 is the apex [1], rowIndex = 3 is [1, 3, 3, 1], and row rowIndex holds rowIndex + 1 values.
As a reminder, every row starts and ends with 1, and each interior value is the sum of the two values directly above it.
The twist that makes this worth redoing: produce the row using only O(rowIndex) extra space — building the whole triangle is the easy way out.
Example 1:
Input: rowIndex = 3
Output: [1, 3, 3, 1]
Explanation: Row 3 (counting from 0) of the triangle is [1, 3, 3, 1].
Example 2:
Input: rowIndex = 0
Output: [1]
Explanation: Row 0 is the apex of the triangle.
Constraints:
- 0 ≤ rowIndex ≤ 33
Hints:
You could build every row up to rowIndex like in Pascal's Triangle and return the last one — correct, but it stores the whole triangle.
A single array can host the evolution. Start with all 1s and, for each new row, update positions from right to left: row[k] += row[k-1]. Going rightward first would overwrite a value you still need.
Row n is C(n, 0) … C(n, n), and C(n, k) = C(n, k-1) · (n - k + 1) / k builds the row in one left-to-right sweep — O(rowIndex) time, no predecessor row at all.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: rowIndex = 3
Expected output: [1, 3, 3, 1]