Pascal's Triangle
Pascal's Triangle is LeetCode 118 (Easy). You are given an integer numRows and must return the first numRows rows of Pascal's triangle as a list of lists.
- Row
i(counting from 0) hasi + 1numbers. - The first and last number of every row is
1. - Every other number is the sum of the two numbers directly above it in the previous row.
numRows is between 1 and 30, so the whole triangle is at most 465 numbers. The Pascal's triangle LeetCode task is really about building each row cleanly from the one before it, not about speed.
- 1 <= numRows <= 30
Intuition
Pascal's triangle explained in one sentence: every row is built from the row above it, and from nothing else. Each inner entry is the sum of the two entries above it, and both ends are always 1.
The Pascal triangle formula explains why the sum works. Entry j of row i is the binomial coefficient C(i, j) = i! / (j! (i − j)!), the number of ways to choose j items from i. Any such choice either includes the last item, leaving C(i−1, j−1) ways to pick the rest, or skips it, leaving C(i−1, j) ways. Those two counts are exactly the two numbers sitting above the entry.
When each value in a table depends only on neighbours in the previous row, build it row by row and keep just the last row. Unique Paths (62) counts grid paths with the same addition, and any question about C(n, k) for small n can read the answer straight from the triangle.
Approach
Before reading on, write row 5 using only row 4 ([1, 4, 6, 4, 1]). Then decide how many additions building numRows rows takes in total.
Start each row as all 1s
In the Pascal's triangle Python code, row i is created as [1] * (i + 1), a fresh list each time. That sets both ends correctly and leaves the inner slots to be overwritten. Rows 0 and 1 have no inner slots, so they are finished immediately.
Fill the inner entries from the previous row
For j from 1 to i − 1, set row[j] = prev[j - 1] + prev[j]. The previous row is already complete, so both parents are final, and reading from prev rather than the row being written means no value is overwritten before it is used.
Append and repeat
Append the finished row to the result and keep it as prev for the next row. After numRows rows, return the whole list. Each entry is computed once from two lookups, so time and output size are both O(numRows²).
Pascal's Triangle solution in Python | C++ | Java
[1]. Every row starts and ends with 1, and row i has i + 1 entries. Creating each row as all 1s handles both ends at once; only the inner entries need work.[1, 1]. Both entries are ends, so there is nothing to add. The first sum appears in row 2.[1]. Every row starts and ends with 1, and row i has i + 1 entries. Creating each row as all 1s handles both ends at once; only the inner entries need work.[1, 1]. Both entries are ends, so there is nothing to add. The first sum appears in row 2.[1]. Every row starts and ends with 1, and row i has i + 1 entries. Creating each row as all 1s handles both ends at once; only the inner entries need work.[[1]].Common pitfalls
Looping j over the ends too
for j in range(0, i + 1):
row[j] = prev[j - 1] + prev[j]for j in range(1, i):
row[j] = prev[j - 1] + prev[j]At j = 0, prev[-1] silently reads the last element in Python, and at j = i, prev[i] is out of range. The ends have only one parent, so they stay 1.
Sharing one list between rows
row = [1]
for i in range(numRows):
triangle.append(row)
row.append(1)for i in range(numRows):
row = [1] * (i + 1)
triangle.append(row)Appending the same list object means every row in the result is the same list, and all of them show the last row. Each row must be a new list.
Computing each entry from factorials
row[j] = factorial(i) // (factorial(j) * factorial(i - j))
row[j] = prev[j - 1] + prev[j]
It is O(i) work per entry instead of O(1), and in C++ or Java the factorials overflow long before the entries do: 21! does not fit in 64 bits, while row 30 still fits in an int.
Complexity
Pascal's Triangle vs Pascal's Triangle II
LeetCode has two versions. The rule is the same; what they return, and so what memory they need, differs.
| Pascal's Triangle (118) | Pascal's Triangle II (119) | |
|---|---|---|
| Returns | all rows 0 to numRows − 1 | only row rowIndex |
| Memory | O(n²), the output | O(n): one row updated in place |
| In-place trick | not needed | update row[j] += row[j-1] from right to left |
| Direct formula | not needed | C(n, k+1) = C(n, k) × (n − k) / (k + 1) |
Pascal's Triangle FAQ
What is Pascal's triangle?
A triangle of numbers where each row starts and ends with 1 and every inner number is the sum of the two above it. Row n lists the binomial coefficients C(n, 0) to C(n, n). It is named after Blaise Pascal, though it was known centuries earlier in India, Persia and China.
What patterns are in Pascal's triangle?
- Each row reads the same forwards and backwards.
- Row
nsums to 2ⁿ. - The second diagonal is 1, 2, 3, 4…, the third is the triangular numbers 1, 3, 6, 10….
- Row
ngives the coefficients of (a + b)ⁿ, the binomial theorem. - Rows 0 to 4 read as numbers are powers of 11: 1, 11, 121, 1331, 14641.
What is Pascal's triangle used for?
Expanding (a + b)ⁿ, counting combinations C(n, k), probabilities for coin flips (row n counts the ways to get k heads in n flips), and counting lattice paths through a grid.