☕ DSA Java Articles

Topics › Arrays › Hard

Pascal's Triangle I

Easy TUF ID 813 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Pascal’s triangle is the triangular arrangement of numbers in which every row starts and ends with 1, and every other entry is the sum of the two entries directly 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

Rows and columns are 1-indexed in this article. The sheet poses the same picture as three separate questions, and all three are covered here:

  1. Element. Given r and c, return the value at row r, column c.
  2. Row. Given r, return the whole row r.
  3. Triangle. Given n, return the first n rows. This is the LeetCode version.

Constraints: 1 ≤ c ≤ r ≤ 30 for the element and row variants on the sheet, 1 ≤ n ≤ 30 for the triangle. Values are returned as long. The addition-based methods stay exact up to row 67; the multiplicative formulas below have intermediate products roughly r times larger than the answer and stay exact up to about row 62. Both are far beyond the sheet’s limit of 30.

Example 1

r = 5, c = 3
answer = 6               // row 5 is 1 4 6 4 1

Example 2

n = 5
answer = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

The one fact behind everything

The entry at row r, column c is the binomial coefficient C(r - 1, c - 1), the number of ways to choose c - 1 items out of r - 1. The addition rule of the triangle is exactly Pascal’s identity C(n, k) = C(n - 1, k - 1) + C(n - 1, k), and the boundary 1s are C(n, 0) = C(n, n) = 1. Every approach below is either “apply the addition rule” or “evaluate C(n, k) directly”.

Computing C(n, k) with factorials overflows almost immediately (21! does not fit in a long). The safe way is the running product

C(n, k) = (n / 1) × ((n - 1) / 2) × ((n - 2) / 3) × ... × ((n - k + 1) / k)

evaluated left to right, multiplying before dividing. After i factors the running value is exactly C(n, i), an integer, so each division is exact and the intermediate values stay as small as the answer itself (times at most n).

static long nCr(int n, int k) {
    if (k < 0 || k > n) return 0;
    k = Math.min(k, n - k);                     // C(n, k) == C(n, n-k): use the shorter loop
    long res = 1;
    for (int i = 0; i < k; i++) {
        res = res * (n - i) / (i + 1);
    }
    return res;
}

Variant 1: a single element

Approach 1: Build the rows

Intuition. Generate row 1, then row 2 from row 1, and so on up to row r using the addition rule, then read the c-th entry. Each row is built from the previous one, so only one previous row needs to be kept.

Algorithm.

  1. Start with row = [1].
  2. For i from 2 to r: build next of length i with 1s at both ends and next[j] = row[j-1] + row[j] in between; set row = next.
  3. Return row[c - 1].
static long elementBrute(int r, int c) {
    long[] row = {1};
    for (int i = 2; i <= r; i++) {
        long[] next = new long[i];
        next[0] = 1;
        next[i - 1] = 1;
        for (int j = 1; j < i - 1; j++) next[j] = row[j - 1] + row[j];
        row = next;
    }
    return row[c - 1];
}

Complexity. Time O(r^2): row i costs O(i). Space O(r) for the current row.

Approach 2: Direct formula

Intuition. The element is C(r - 1, c - 1), so compute it with the running product. No other row is needed.

static long elementOptimal(int r, int c) {
    return nCr(r - 1, c - 1);
}

Complexity. Time O(c) (or O(r - c) thanks to the symmetry trick, whichever is smaller). Space O(1).

Variant 2: one full row

Approach 1: nCr for every column

Intuition. Row r is C(r-1, 0), C(r-1, 1), ..., C(r-1, r-1). Calling nCr once per column is correct and simple.

static long[] rowBrute(int r) {
    long[] row = new long[r];
    for (int c = 1; c <= r; c++) row[c - 1] = nCr(r - 1, c - 1);
    return row;
}

Complexity. Time O(r^2): r calls, each up to O(r). Space O(r) for the answer.

Approach 2: Each entry from the previous one

Intuition. Adjacent entries of a row are related by C(n, c) = C(n, c - 1) × (n - c + 1) / c. With n = r - 1 this reads row[c] = row[c - 1] × (r - c) / c for 0-indexed c. Starting from row[0] = 1, the whole row follows in one pass, and because each row[c] is itself a binomial coefficient the division is exact. Checking on row 5: 1, 1×4/1 = 4, 4×3/2 = 6, 6×2/3 = 4, 4×1/4 = 1.

static long[] rowOptimal(int r) {
    long[] row = new long[r];
    row[0] = 1;
    for (int c = 1; c < r; c++) {
        row[c] = row[c - 1] * (r - c) / c;
    }
    return row;
}

Complexity. Time O(r). Space O(r) for the answer, O(1) otherwise.

Variant 3: the first n rows

Approach 1: nCr for every cell

Intuition. Fill every cell (r, c) with C(r - 1, c - 1) independently.

static long[][] triangleBrute(int n) {
    long[][] tri = new long[n][];
    for (int r = 1; r <= n; r++) {
        tri[r - 1] = new long[r];
        for (int c = 1; c <= r; c++) tri[r - 1][c - 1] = nCr(r - 1, c - 1);
    }
    return tri;
}

Complexity. Time O(n^3): O(n^2) cells, each up to O(n). Space O(n^2) for the answer.

Approach 2: Addition rule, row by row

Intuition. Since we are producing every row anyway, the previous row is always available, and the addition rule gives each inner cell in O(1). This is the classic LeetCode solution.

Algorithm.

  1. For r from 0 to n - 1 (0-indexed here): allocate a row of length r + 1 with 1 at both ends.
  2. For c from 1 to r - 1: tri[r][c] = tri[r-1][c-1] + tri[r-1][c].
static long[][] triangleOptimal(int n) {
    long[][] tri = new long[n][];
    for (int r = 0; r < n; r++) {
        tri[r] = new long[r + 1];
        tri[r][0] = 1;
        tri[r][r] = 1;
        for (int c = 1; c < r; c++) tri[r][c] = tri[r - 1][c - 1] + tri[r - 1][c];
    }
    return tri;
}

Dry run for n = 5:

r (0-indexed) built from previous row row
0 - [1]
1 ends only [1, 1]
2 1 + 1 [1, 2, 1]
3 1 + 2, 2 + 1 [1, 3, 3, 1]
4 1 + 3, 3 + 3, 3 + 1 [1, 4, 6, 4, 1]

Complexity. Time O(n^2), which is optimal because the output itself has n(n+1)/2 cells. Space O(n^2) for the answer.

Edge cases and pitfalls