118. Pascal's Triangle
Pascal's triangle starts with a single 1 on top. Every later row begins and ends with 1, and each interior entry is the sum of the two entries sitting directly above it.
Your function receives an integer numRows and returns the first numRows rows of the triangle as a list of lists — row 1 is [1], row 2 is [1, 1], and so on.
This is dynamic programming at its friendliest: each row is fully determined by the row before it.
Example 1:
Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explanation: Each interior value is the sum of its two upstairs neighbors: in row 5, 4 = 1 + 3 and 6 = 3 + 3.
Example 2:
Input: numRows = 1
Output: [[1]]
Explanation: One row: just the apex.
Constraints:
- 1 ≤ numRows ≤ 30
Hints:
Row k has k entries. Its first and last are always 1; entry j (0-indexed, interior) is prev[j - 1] + prev[j] where prev is the row above.
You never need more history than the single previous row — build rows one at a time and append each to the answer.
Interior entries are binomial coefficients: row n (0-indexed) is C(n, 0) … C(n, n), and C(n, k) = C(n, k-1) · (n - k + 1) / k lets you produce a row without looking at the previous one.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: numRows = 5
Expected output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]