106. Pascal's Triangle

Each interior entry is the sum of the two entries directly above it; the ends are always 1.

Build each row from the previous

Row 0 is [1]. For each next row, the first and last entries are 1, and each interior entry row[c] equals prev[c-1] + prev[c].

row[0] = row[r] = 1
row[c] = prev[c-1] + prev[c]   (0 < c < r)

Worked example

numRows = 5:

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]

Complexity

• Time: O(numRows²).
• Space: O(numRows²) for the output.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> tri = 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);
                } else {
                    row.add(tri.get(r - 1).get(c - 1) + tri.get(r - 1).get(c));
                }
            }
            tri.add(row);
        }
        return tri;
    }
}