Pascal's Triangle

Easy Dynamic Programming 1D DP Original on LeetCode

Pascal's Triangle is a easy dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (build each row from the previous one), runs in O(n²) time and O(1) extra space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (binomial coefficient for every cell) up.

Problem

Given an integer numRows, build the first numRows rows of Pascal’s triangle and return them as a list of rows.

Row 0 is [1]. Each following row is one entry longer: it starts and ends with 1, and every entry in between is the sum of the two entries that sit directly above it (to the upper-left and upper-right) in the previous row.

Examples

Example 1

Input
numRows = 4
Output
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
Why
Each inner value is the sum of the two values just above it, e.g. 3 = 1 + 2.

Example 2

Input
numRows = 2
Output
[[1], [1, 1]]
Why
The first two rows have no inner values; every entry is an edge 1.

Constraints

  • 1 <= numRows <= 30

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (binomial coefficient for every cell)O(n³)O(1) extra
Optimal (build each row from the previous one)O(n²)O(1) extra

1Brute force (binomial coefficient for every cell)

TimeO(n³)There are about n²/2 cells and each one costs up to O(n) multiplications.
SpaceO(1) extraApart from the output, only a few counters are used.

Entry j of row r is the binomial coefficient C(r, j). Compute each one independently with a small multiplicative loop.

  1. For each row r from 0 to numRows - 1 and each j from 0 to r:
  2. Compute C(r, j) by multiplying c = c * (r - k) / (k + 1) for k from 0 to j - 1, using a long.
  3. Append the value to the row; append the row to the answer.
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int r = 0; r < numRows; r++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= r; j++) {
                long c = 1;
                for (int k = 0; k < j; k++) {
                    c = c * (r - k) / (k + 1);
                }
                row.add((int) c);
            }
            res.add(row);
        }
        return res;
    }
}

2Optimal (build each row from the previous one)

TimeO(n²)Each of the roughly n²/2 cells is computed once with a single addition.
SpaceO(1) extraOnly the output itself is stored.

Start with [1]. Every new row begins and ends with 1, and its inner entry j is prev[j - 1] + prev[j]. Each cell is filled in O(1).

  1. res = [[1]].
  2. For r from 1 to numRows - 1: let prev = res[r - 1].
  3. row = [1]; for j from 1 to r - 1 append prev[j - 1] + prev[j]; append 1.
  4. Add row to res and return res at the end.
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(List.of(1));
        for (int r = 1; r < numRows; r++) {
            List<Integer> prev = res.get(r - 1);
            List<Integer> row = new ArrayList<>();
            row.add(1);
            for (int j = 1; j < r; j++) {
                row.add(prev.get(j - 1) + prev.get(j));
            }
            row.add(1);
            res.add(row);
        }
        return res;
    }
}

Edge cases to test

  • numRows = 1: only the single row [1]
  • numRows = 30: the largest entries are still below 2^31, so int is enough

Hints

Hint 1

Row r has r + 1 entries, and its first and last entries are always 1.

Hint 2

Every other entry is the sum of the two entries diagonally above it in the previous row.

FAQ

What is the best time complexity for Pascal's Triangle?

Optimal (build each row from the previous one) runs in O(n²) time and O(1) extra extra space. Each of the roughly n²/2 cells is computed once with a single addition.

Which pattern does Pascal's Triangle use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Pascal's Triangle?

Yes. Brute force (binomial coefficient for every cell) takes O(n³) time and O(1) extra space. Entry j of row r is the binomial coefficient C(r, j).

Which edge cases should I test for Pascal's Triangle?

numRows = 1: only the single row [1]; numRows = 30: the largest entries are still below 2^31, so int is enough.