LearnWithKiriti

Pascal's Triangle

Easy LeetCode 118 ↗ GitHub ↗
💻 Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here. 🎮 Play Kodee's Row Rush: a mini-game built on this problem. Works on your phone too. Pass Submit to unlock every round.
Play
On this page
  1. Revision notes
  2. Element: Brute
  3. Element: Optimal
  4. Row: Optimal
  5. Triangle: Optimal
  6. Triangle: Row Formula

Revision notes

Pascal’s Triangle (interview style)

Video: “Pascal’s Triangle” on LearnWithKiriti (Kodee and Mr. Tock). Arrays series, episode 13. LeetCode 118, Easy. Taught as the three ways interviewers ask it: one number, one row, the whole triangle.

Every row starts and ends with 1, and every number inside is the sum of the two numbers above it.

row 1:        1
row 2:       1 1
row 3:      1 2 1
row 4:     1 3 3 1
row 5:    1 4 6 4 1

LeetCode 118: numRows = 5 -> [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]].

Folder Question Approach Time Extra space
Element-Brute/ The number at (row, col) n C r with factorials. Right on paper, but long breaks at 21!: row 22, column 2 prints -1 in Java O(row) O(1)
Element-Optimal/ The number at (row, col) ans = ans * (row - step) / step, multiply first, then divide O(col) O(1)
Row-Optimal/ One whole row (LeetCode 119 style) Walk along the row: ans = ans * (row - col) / col O(row) O(1) (the answer list is not counted)
Triangle-Optimal/ The whole triangle (LeetCode 118) Add the two above, 1 at both ends O(n^2) O(1) (the answer is not counted)
Triangle-RowFormula/ The whole triangle (LeetCode 118) Call the row formula for every row O(n^2) O(1) (the answer is not counted)

Rows and columns count from 1, the way interviewers usually say them, so the number at (row, col) is C(row-1, col-1). Example: (5, 3) = C(4, 2) = 6.

Rebuild it

Add the two above. Multiply, then divide. Never a factorial.

  • Every number counts the paths from the top down to it: one path to an edge, and the paths to an inside cell are the paths to its two parents added up. That count is n C r.
  • Next number from the previous one: ans = ans * (row - col) / col. The division is always exact, because after every step ans is itself a binomial (a whole number of paths). Divide first and it breaks: (6, 3) gives 8 instead of 10.
  • Overflow: with a 32-bit int and multiply-then-divide, row index 30 (the 31st row) is the first to overflow (145,422,675 x 16 = 2,326,762,800). LeetCode 118 stops at 30 rows (biggest number C(29,14) = 77,558,760), so int fits. For bigger rows, use long.
  • The whole triangle is O(n^2), and nothing can beat that: the answer itself has n(n+1)/2 numbers.

Practise it next to the video: the free Kodee Practice Chrome extension (link in the video description).

Related: Pascal’s Triangle II (LeetCode 119) is exactly Row-Optimal/.

See the pseudocode.md in each folder. Every program was compiled, run and tested against Python’s math.comb for every row from 1 to 30.

brute

Element: Brute

R1 Brute: the number at (row, col) with factorials

n = row - 1 ; r = col - 1
return n! / ( r! * (n - r)! )

Dry run (5, 3): n = 4, r = 2, n - r = 2 -> 24 / (2 * 2) = 6. Why not: the factorials overflow long before the answer does. int breaks at 13!, long at 21!, so (22, 2), whose answer is 21, prints -1 in Java. Python’s integers never overflow, but the numbers get huge. Complexity: O(row) time, O(1) extra space. The time is fine; the numbers are the problem.

PascalElementBrute.java
import java.util.*;

public class PascalElementBrute {
    // Brute force: n C r with factorials. Correct on paper, but factorials overflow fast.
    // int breaks at 13!, long breaks at 21! (so row 22 already gives a wrong answer).
    static long factorial(int n) {
        long result = 1;
        for (int factor = 2; factor <= n; factor++) {
            result = result * factor;
        }
        return result;
    }

    static long pascalElementBrute(int row, int col) {
        long top = factorial(row - 1);
        long bottom = factorial(col - 1) * factorial(row - col);
        return top / bottom;
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        System.out.println(show(pascalElementBrute(5, 3)));
        System.out.println(show(pascalElementBrute(1, 1)));
        System.out.println(show(pascalElementBrute(6, 3)));
        System.out.println(show(pascalElementBrute(21, 11)));
    }
}
optimal

Element: Optimal

R1 Optimal: the number at (row, col), never a factorial

ans = 1
for step from 1 to col - 1:
    ans = ans * (row - step) / step          (multiply first, then divide)
return ans

Derivation: C(4, 2) = (4 * 3) / (2 * 1). The long factorials cancel, so walk it: x4 / 1, then x3 / 2. Proof the division is exact: after each step, ans = C(row - 1, step), a count of paths, so a whole number. Order matters: (6, 3) is 10; multiply first gives 5 * 4 / 2 = 10, divide first gives 5 / 2 = 2, then 2 * 4 = 8. Dry run (5, 3): step = 1: 1 * 4 / 1 = 4; step = 2: 4 * 3 / 2 = 6; stop -> 6. Column 1: the loop never runs, ans = 1. Symmetry: C(n, r) = C(n, n - r), so you can loop min(col - 1, row - col) steps. (30, 29) = C(29, 1) = 29 in one step. Complexity: O(col) time, O(1) extra space.

PascalElement.java
import java.util.*;

public class PascalElement {
    static long pascalElement(int row, int col) {
        long ans = 1;
        for (int step = 1; step < col; step++) {
            ans = ans * (row - step) / step;
        }
        return ans;
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        System.out.println(show(pascalElement(5, 3)));
        System.out.println(show(pascalElement(1, 1)));
        System.out.println(show(pascalElement(6, 3)));
        System.out.println(show(pascalElement(30, 15)));
        System.out.println(show(pascalElement(31, 16)));
    }
}
optimal

Row: Optimal

R2 Optimal: one whole row (LeetCode 119 style)

list = [1] ; ans = 1
for col from 1 to row - 1:
    ans = ans * (row - col) / col
    list.add(ans)
return list

Derivation: the next number is this number x (row - col) / col. Same exactness proof as R1. Dry run row 5: 1 * 4 / 1 = 4 -> [1, 4]; 4 * 3 / 2 = 6 -> [1, 4, 6]; 6 * 2 / 3 = 4; 4 * 1 / 4 = 1 -> [1, 4, 6, 4, 1]. Row 1: the loop never runs -> [1]. Brute force (not coded): call R1 for every column, O(row^2), because every call repeats the earlier steps. Overflow: with a 32-bit int, row index 29 still fits (77,558,760 x 15 = 1,163,381,400), but row index 30 breaks (145,422,675 x 16 = 2,326,762,800 > 2,147,483,647), even though its biggest answer, 155,117,520, fits. That is why ans is a long. Why O(row) and not O(1): the row itself has row numbers. Complexity: O(row) time, O(1) extra space besides the output.

GenerateRow.java
import java.util.*;

public class GenerateRow {
    static List<Integer> generateRow(int row) {
        List<Integer> rowList = new ArrayList<>();
        rowList.add(1);
        long ans = 1;
        for (int col = 1; col < row; col++) {
            ans = ans * (row - col) / col;
            rowList.add((int) ans);
        }
        return rowList;
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        System.out.println(show(generateRow(5)));
        System.out.println(show(generateRow(1)));
        System.out.println(show(generateRow(2)));
        System.out.println(show(generateRow(7)));
    }
}
optimal

Triangle: Optimal

R3 Optimal: the whole triangle (LeetCode 118), add the two above

triangle = []
for row from 0 to numRows - 1:                 (0-indexed loop counters)
    rowList = []
    for col from 0 to row:
        if col == 0 or col == row: rowList.add(1)
        else: prev = triangle[row - 1]; rowList.add(prev[col - 1] + prev[col])
    triangle.add(rowList)
return triangle

Why the 1s at both ends: an edge cell has only one parent. Pretend there is an invisible zero outside the triangle: 1 + 0 = 1. Dry run numRows 5: [1]; [1, 1]; [1, 2, 1]; [1, 3, 3, 1]; [1, 4, 6, 4, 1]. numRows 1 -> [[1]] (prev is never touched). Only additions, so no middle step is ever bigger than the answer (an int is safe up to row index 33). Complexity: the answer holds n(n+1)/2 numbers (30 rows: 465), so O(n^2) time is the best possible; O(1) extra space besides the output.

Generate.java
import java.util.*;

public class Generate {
    static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        for (int row = 0; row < numRows; row++) {
            List<Integer> rowList = new ArrayList<>();
            for (int col = 0; col <= row; col++) {
                if (col == 0 || col == row) {
                    rowList.add(1);
                } else {
                    List<Integer> prev = triangle.get(row - 1);
                    rowList.add(prev.get(col - 1) + prev.get(col));
                }
            }
            triangle.add(rowList);
        }
        return triangle;
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        System.out.println(show(generate(5)));
        System.out.println(show(generate(1)));
        System.out.println(show(generate(2)));
    }
}
other

Triangle: Row Formula

R3 the other way: build every row with the row formula

for row from 1 to numRows:
    triangle.add(generateRow(row))           (R2's formula for each row)
return triangle

Dry run numRows 3: generateRow(1) = [1], generateRow(2) = [1, 1], generateRow(3) = [1, 2, 1]. Complexity: O(n^2) time, the same as adding the two above. It needs a long for the middle steps (see Row-Optimal), which is why the video types the “add the two above” version.

GenerateByRowFormula.java
import java.util.*;

public class GenerateByRowFormula {
    // LeetCode 118, version (b): build every row with the round two formula.
    static List<Integer> generateRow(int row) {
        List<Integer> rowList = new ArrayList<>();
        rowList.add(1);
        long ans = 1;
        for (int col = 1; col < row; col++) {
            ans = ans * (row - col) / col;
            rowList.add((int) ans);
        }
        return rowList;
    }

    static List<List<Integer>> generateByRowFormula(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        for (int row = 1; row <= numRows; row++) {
            triangle.add(generateRow(row));
        }
        return triangle;
    }

    static String show(Object o) {
        if (o instanceof int[]) return java.util.Arrays.toString((int[]) o);
        if (o instanceof long[]) return java.util.Arrays.toString((long[]) o);
        if (o instanceof boolean[]) return java.util.Arrays.toString((boolean[]) o);
        if (o instanceof Object[]) return java.util.Arrays.deepToString((Object[]) o);
        return String.valueOf(o);
    }

    public static void main(String[] args) {
        System.out.println(show(generateByRowFormula(5)));
        System.out.println(show(generateByRowFormula(1)));
        System.out.println(show(generateByRowFormula(2)));
    }
}