Pascal's Triangle II

Easy Dynamic Programming 1D DP Original on LeetCode

Reported atOlaAirtel

Pascal's Triangle II is a easy dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (binomial coefficients), runs in O(k) time and O(k) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (build the whole triangle) up.

Problem

The binomial triangle (each row lists the binomial coefficients) starts with a single 1 at the top. Every following row begins and ends with 1, and each inner number equals the sum of the two numbers directly above it.

Given an integer rowIndex, return row number rowIndex of the triangle (rows are numbered from 0).

Examples

Example 1

Input
rowIndex = 4
Output
[1, 4, 6, 4, 1]
Why
Row 3 is [1, 3, 3, 1]; each inner entry of row 4 is the sum of the two entries above it: 1+3, 3+3, 3+1.

Example 2

Input
rowIndex = 0
Output
[1]
Why
Row 0 is the single 1 at the top of the triangle.

Example 3

Input
rowIndex = 6
Output
[1, 6, 15, 20, 15, 6, 1]
Why
Row 5 is [1, 5, 10, 10, 5, 1], and adding neighbours gives 6, 15, 20, 15, 6 between the two outer 1s.

Constraints

  • 0 <= rowIndex <= 33
  • Use only O(rowIndex) extra space for the follow-up.

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 (3 examples, or your own). Submit also runs 9 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 (build the whole triangle)O(k²)O(k²)
Better (one row updated in place)O(k²)O(k)
Optimal (binomial coefficients)O(k)O(k)

1Brute force (build the whole triangle)

TimeO(k²)Rows 0..k have 1 + 2 + … + (k + 1) entries in total.
SpaceO(k²)All rows are kept.

Generate every row from 0 up to rowIndex, each from the one before it, storing the full triangle. Return the last row.

  1. Start with the row [1].
  2. For each next row, put 1 at both ends and prev[j - 1] + prev[j] in between.
  3. Store each row in a list of rows and return the last one.
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> rows = new ArrayList<>();
        rows.add(List.of(1));
        for (int k = 1; k <= rowIndex; k++) {
            List<Integer> prev = rows.get(k - 1);
            List<Integer> row = new ArrayList<>();
            row.add(1);
            for (int j = 1; j < k; j++) row.add(prev.get(j - 1) + prev.get(j));
            row.add(1);
            rows.add(row);
        }
        return new ArrayList<>(rows.get(rowIndex));
    }
}

2Better (one row updated in place)

TimeO(k²)Row k still needs about k additions, for every row up to k.
SpaceO(k)Only one row of k + 1 values is stored.

Keep a single array. To move from row k - 1 to row k, append a 1 and then update the inner entries from right to left with row[j] += row[j - 1]. Going right to left means row[j - 1] still holds the old value when it is read.

  1. row = [1].
  2. Repeat rowIndex times: append 1, then for j from len - 2 down to 1, row[j] += row[j - 1].
  3. Return row.
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1);
        for (int k = 1; k <= rowIndex; k++) {
            row.add(1);
            for (int j = k - 1; j >= 1; j--) row.set(j, row.get(j) + row.get(j - 1));
        }
        return row;
    }
}

3Optimal (binomial coefficients)

TimeO(k)One multiplication and one division per entry.
SpaceO(k)Only the output row is stored.

Entry i of row k is C(k, i). Consecutive coefficients are related by C(k, i) = C(k, i - 1) · (k - i + 1) / i, and that division is always exact. So the row can be produced left to right in a single pass. Use a 64-bit value for the multiplication before dividing.

  1. value = 1; add it to the row.
  2. For i from 1 to k: value = value · (k - i + 1) / i (64-bit); add it.
  3. Return the row.
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        long value = 1;
        row.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            value = value * (rowIndex - i + 1) / i;
            row.add((int) value);
        }
        return row;
    }
}

Edge cases to test

  • rowIndex = 0 and rowIndex = 1
  • The largest row, whose middle value (1166803110) is close to the 32-bit limit

Hints

Hint 1

Row k has k + 1 entries; both ends are 1 and every inner entry is the sum of the two entries above it.

Hint 2

You only need the previous row to build the next one. Can you update a single array in place if you go from right to left?

Hint 3

Entry i of row k is the binomial coefficient C(k, i), and C(k, i) = C(k, i - 1) · (k - i + 1) / i.

FAQ

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

Optimal (binomial coefficients) runs in O(k) time and O(k) extra space. One multiplication and one division per entry.

Which pattern does Pascal's Triangle II 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 II?

Yes. Brute force (build the whole triangle) takes O(k²) time and O(k²) space. Generate every row from 0 up to rowIndex, each from the one before it, storing the full triangle.

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

rowIndex = 0 and rowIndex = 1; The largest row, whose middle value (1166803110) is close to the 32-bit limit.