DSA problem
Pascal's Triangle
Given an integer numRows, return the first numRows of Pascal's triangle. Each row is a list of integers; the triangle as a whole is a list of lists, with row i containing exactly i + 1 entries.
Pascal's triangle is built by a simple geometric rule: every interior entry is the sum of the two entries directly above it in the previous row, while the first and last entries of every row are always 1. So row 0 is [1], row 1 is [1, 1], row 2 is [1, 2, 1], row 3 is [1, 3, 3, 1], and so on. The same numbers arise as binomial coefficients C(n, k), and they show up everywhere from combinatorics to probability to polynomial expansion.
A direct approach is to compute each entry as a binomial coefficient using factorials. That works for small inputs but quickly overflows for larger rows and recomputes the same factorials many times. It is also overkill: the recurrence C(n, k) = C(n - 1, k - 1) + C(n - 1, k) is exactly the row-by-row construction rule, so building the triangle is itself the natural DP.
The optimal approach treats each row as the result of a tiny 1-D DP over the previous row. Starting from [1], repeatedly build the next row by setting row[0] = row[-1] = 1 and row[j] = prev[j - 1] + prev[j] for the interior positions. This produces numRows rows in O(numRows^2) time and O(numRows^2) space (counting the output itself), with no overflow risk and only addition.
Examples
numRows = 5[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]numRows = 1[[1]]numRows = 3[[1],[1,1],[1,2,1]]Constraints
- 1 <= numRows <= 30
- Each value fits comfortably in a 32-bit signed integer for the allowed range.
- The output must contain exactly `numRows` rows.
- Row `i` (0-indexed) contains exactly `i + 1` entries.
- The first and last entry of every row is 1.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.