Pascal's Triangle LeetCode 118 Deep Dive

LeetCode 118 Pascal's Triangle asks you to generate the first numRows rows of Pascal's triangle and return them as a list of lists. Each row is a list of integers, and the overall result is a list of those rows in order from row 0 at the top to row numRows-1 at the bottom.

The defining rule is simple: the first and last element of every row is always 1, and every element in between is the sum of the two elements directly above it in the previous row. This recurrence is what makes Pascal's triangle both easy to compute and mathematically rich.

The problem is tagged Easy on LeetCode but rewards deep understanding. The same triangle encodes binomial coefficients, powers of 11, Fibonacci numbers in diagonal sums, and fractal patterns under modular arithmetic — all emerging from a single three-line rule.

The construction starts with row 0 = [1]. To build each subsequent row, begin with 1, compute each middle element as prevRow[j-1] + prevRow[j] for j from 1 to len(prevRow)-1, then append a final 1. Append the new row to the result and repeat.

This approach reads one row and writes the next in a single pass, making it cache-friendly and easy to reason about. Each row depends only on the immediately preceding row, so you only need to keep the previous row in memory at any moment — though the problem asks you to return all rows, so you accumulate them all in the result list.

The total work is proportional to the total number of elements produced: 1 + 2 + 3 + ... + numRows = numRows*(numRows+1)/2, which is O(numRows^2). This is optimal because you must produce that many elements in the output regardless of algorithm.

The algorithm initializes the result with the first row [[1]], then iterates from row index 1 up to numRows-1. For each row, it reads the previous row and constructs the new row element by element.

The inner loop runs from j=1 to j=len(prev)-1 (exclusive), computing newRow[j] = prev[j-1] + prev[j]. This handles all interior elements. The leading and trailing 1s are appended manually before and after the loop.

After constructing the new row, append it to the result list and move on. The outer loop runs numRows-1 times, and the inner loop grows by one iteration each time, giving the quadratic total work that matches the output size.

Every element in Pascal's triangle is a binomial coefficient. Row n, position k (both zero-indexed) equals C(n,k) = n! / (k! * (n-k)!). So row 4 reads [C(4,0), C(4,1), C(4,2), C(4,3), C(4,4)] = [1, 4, 6, 4, 1], which is exactly what the construction algorithm produces.

The recurrence that drives the construction — element = sum of two above — is Pascal's identity: C(n,k) = C(n-1,k-1) + C(n-1,k). This means building Pascal's triangle row by row is equivalent to computing all binomial coefficients using dynamic programming on Pascal's identity instead of evaluating factorials.

This connection explains why the triangle appears in so many combinatorial formulas. The number of ways to choose k items from n is encoded directly in row n, position k. Any algorithm that counts subsets, paths, or binary strings of fixed length is secretly reading a value from Pascal's triangle.

Starting from [1], apply the construction rule four times to build rows 1 through 4. Each step reads the previous row and computes the next by summing adjacent pairs and bookending with 1s.

Row 2 comes from row 1: [1, 1+1, 1] but middle only has j=1..0 which is empty, so [1, 1+1... wait — row 1 is [1,1], so j=1 to 0 is empty, giving [1, 1] with no interior. Row 2 from [1,1]: j=1..0 — actually j from 1 to i-1=1 inclusive: j=1, newRow[1]=prev[0]+prev[1]=1+1=2, so row 2 = [1, 2, 1]. Continue applying the same rule for rows 3 and 4.

The five rows together form the familiar shape [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]. Each middle element is visible as the sum of its two parents: 2=1+1, 3=1+2=2+1, 6=3+3, 4=1+3=3+1.

Python solution: def generate(numRows): result = [[1]]; for i in range(1, numRows): prev = result[-1]; row = [1] + [prev[j-1]+prev[j] for j in range(1,i)] + [1]; result.append(row); return result. The list comprehension builds all interior elements in one expression, and the leading/trailing 1s are concatenated. O(n^2) time, O(n^2) space for the output.

Java solution: List<List<Integer>> result = new ArrayList<>(); result.add(Arrays.asList(1)); for (int i = 1; i < numRows; i++) { List<Integer> prev = result.get(i-1); List<Integer> row = new ArrayList<>(); row.add(1); for (int j = 1; j < i; j++) row.add(prev.get(j-1)+prev.get(j)); row.add(1); result.add(row); } return result. The logic is identical; Java requires explicit list construction.

Both solutions run in O(n^2) time and O(n^2) space, where n = numRows. The space is dominated by the output itself — every row must be stored. No extra memory beyond the output is needed.

Unique Paths (LeetCode 62) asks for the number of paths in an m x n grid moving only right or down. The answer is C(m+n-2, m-1), which is an entry in Pascal's triangle at row m+n-2, position m-1. Recognizing this connection turns a DP problem into a single combinatorial lookup.

Climbing Stairs (LeetCode 70) produces the Fibonacci sequence, which appears as diagonal sums in Pascal's triangle. Tribonacci and its relatives are also encoded in higher-order diagonals. These connections reveal that many DP recurrences are secretly computing slices or sums of Pascal's triangle.

The broader mathematical DP family — coin change, knapsack, subset sum — all use recurrences that can be visualized as filling a table row by row, mirroring the Pascal construction. Mastering the row-by-row build pattern here is the foundation for understanding why DP tables look the way they do across the entire problem family.