50. Triangle of Sums
A game designer wants a number triangle for a puzzle board. Row 1 contains just the number 1. Every later row has one more entry than the row above it. The first and last entry of each row are 1, and every entry in between is the sum of the two entries directly above it, that is, the entry above and to the left plus the entry above and to the right.
Given n, return the first n rows of the triangle as a list of lists, where row i (counting from 1) has exactly i numbers.
Build each row from the previous one; do not recompute earlier rows.
Example 1
- Input:
- n = 4
- Output:
- [[1],[1,1],[1,2,1],[1,3,3,1]]
- Explanation:
The rows are [1], [1, 1], [1, 2, 1] and [1, 3, 3, 1]; each middle entry is the sum of the two entries above it.
Example 2
- Input:
- n = 1
- Output:
- [[1]]
- Explanation:
Only the first row, which is just [1].
Constraints
1 ≤ n ≤ 30
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n^2)
- Space
- O(n^2) for the output