Pascal's Triangle

Given an integer numRows, return the first numRows rows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it, and each row starts and ends with 1. This is LeetCode 118.

The first rows of Pascal's triangle
Example 1
Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Example 2
Input: numRows = 1
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 - 1 and c of row r - 1.

Each inner value is the sum of the two values above it

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 rRow aboveInner valuesRow
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 also covers row 0, where both are the same position.

Java
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, PascalsTriangle.java, is on GitHub.

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 Unique Paths.