Pascal's Triangle
Understanding the Problem
We need to build Pascal's triangle row by row. Each row starts and ends with 1, and every element in between is the sum of the two elements directly above it from the previous row.
Row 0 is [1]. Row 1 is [1, 1]. For row 2, the edges are 1, and the middle element is 1 + 1 = 2, giving [1, 2, 1]. Row 3 takes the middle values from row 2: 1 + 2 = 3 and 2 + 1 = 3, producing [1, 3, 3, 1].
Row i has exactly i + 1 elements, and element j in row i (where j is not the first or last) equals row[i-1][j-1] + row[i-1][j]. This dependency on the previous row is what drives the solution.
Key Constraints:
1 <= numRows <= 30→ With numRows at most 30, the total number of elements is at most 465. Even an O(n^3) approach would be trivially fast. There is no performance pressure here.- The output is a 2D list of integers, so we need to build the triangle as a list of lists.
- Values stay within 32-bit integer range. The largest value in the triangle is C(29, 14) = 77,558,760, well below the int32 limit of about 2.1 billion.
Approach 1: Iterative Row-by-Row Construction
Intuition
Build Pascal's triangle the same way you'd draw it by hand. Start with the first row [1], then generate each subsequent row from the one before it.
For each new row, the first and last elements are always 1. Each interior element is the sum of the two values directly above it in the previous row. A single nested loop produces the whole triangle.
Algorithm
- Initialize the result with the first row
[[1]]. - For each row index
ifrom 1 tonumRows - 1: - Create a new row starting with
[1]. - For each position
jfrom 1 toi - 1, compute the value aspreviousRow[j-1] + previousRow[j]and append it. - Append 1 at the end of the row.
- Add the completed row to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n^2). We generate n rows, and row i has i+1 elements. The total work is 1 + 2 + ... + n = n(n+1)/2, which is O(n^2). Each element takes O(1) to compute.
- Space Complexity: O(n^2). The output itself contains n(n+1)/2 elements. Since the problem asks us to return the entire triangle, O(n^2) space is unavoidable.
This approach is optimal in time, since the output alone contains O(n^2) elements. The next approach reaches the same complexity through a different route: it computes each row from a closed-form binomial formula, without referencing the previous row.
Approach 2: Mathematical (Combinatorial) Construction
Intuition
Every element in Pascal's triangle is a binomial coefficient. Specifically, element j in row i equals C(i, j) = i! / (j! * (i-j)!).
Computing factorials directly would be wasteful and risk overflow, since intermediate factorials grow far faster than the final coefficients. Instead, derive each element from the one before it in the same row using a ratio:
C(i, j) = C(i, j-1) * (i - j + 1) / j
Each row starts with 1 (since C(i, 0) = 1), and multiplying by this ratio produces the next element. The previous row never enters the computation.
The ratio identity follows from the factorial definition. C(n, k) = n! / (k! (n-k)!) and C(n, k-1) = n! / ((k-1)! (n-k+1)!). Dividing the first by the second cancels n! and most of the other factorials, leaving (n-k+1)/k. So C(n, k) = C(n, k-1) * (n-k+1) / k. Starting from C(n, 0) = 1 and chaining this ratio reproduces every coefficient in the row. The integer division is exact at each step because C(n, k) is always a whole number.
Algorithm
- Initialize the result list.
- For each row index
ifrom 0 tonumRows - 1: - Start the row with
[1]. - For each position
jfrom 1 toi, compute the next value aspreviousValue * (i - j + 1) / j. - Add the completed row to the result.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n^2). Same as Approach 1. We still generate n rows with a total of n(n+1)/2 elements. Each element takes O(1) to compute.
- Space Complexity: O(n^2). The output contains n(n+1)/2 elements. The only extra space beyond the output is O(n) for the current row.