Pascal's Triangle
Given an integer numRowsnumRows
Example 1
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Example 2
Output: [[1]]
How to Think About It
Step 1: Line the rows up on the left
Drawn as a triangle, "the two numbers above" sit diagonally. Written as left-aligned lists, row r has r + 1 values, and the two values above position c of row r are positions c - 1c
Step 2: The rule
- positions 0 and r are 1 (the edges);
- every other position:
.row[c] = above[c - 1] + above[c]
Step 3: Build row by row
Each row needs only the row just above it, which is already in the result list.
Walkthrough
| Row r | Row above | Inner values | Row |
|---|---|---|---|
| 0 | [1] | ||
| 1 | [1] | none | [1, 1] |
| 2 | [1, 1] | 1 + 1 | [1, 2, 1] |
| 3 | [1, 2, 1] | 1 + 2, 2 + 1 | [1, 3, 3, 1] |
| 4 | [1, 3, 3, 1] | 1 + 3, 3 + 3, 3 + 1 | [1, 4, 6, 4, 1] |
Java Solution
The edge check c == 0 || c == r
import java.util.ArrayList;
import java.util.List;
public class PascalsTriangle {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> rows = new ArrayList<>();
for (int r = 0; r < numRows; r++) {
List<Integer> row = new ArrayList<>();
for (int c = 0; c <= r; c++) {
if (c == 0 || c == r) {
row.add(1); // the edges are always 1
} else {
List<Integer> above = rows.get(r - 1);
row.add(above.get(c - 1) + above.get(c));
}
}
rows.add(row);
}
return rows;
}
}
The original implementation,
Complexity
- Time: O(numRows²): one addition per value.
- Space: O(numRows²) for the output.
The value at row r, position c is the binomial coefficient "r choose c", which is why the triangle also counts paths in