Pascal’s triangle

Medium TimeO(n²) SpaceO(n²)

Given a row count n, return the first n rows of Pascal’s triangle as an array of arrays. Counting rows from 0, row i holds i + 1 numbers. The first and last number of every row is 1, and every number between them is the sum of the two directly above it.

Examples

Example 1

Input
n = 6
Output
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
Row 4 reads 1, 4, 6, 4, 1 — the 6 is the 3 and 3 above it added.

Example 2

Input
n = 1
Output
[1]
[[1]]
One row, and with nothing above it both of its ends are the same single 1.

The Code

function pascalsTriangle(n) {
  const triangle = [];
  for (let row = 0; row < n; row++) {
    const line = [];
    for (let col = 0; col <= row; col++) {
      if (col === 0 || col === row) {
        line.push(1);
      } else {
        const above = triangle[row - 1];
        line.push(above[col - 1] + above[col]);
      }
    }
    triangle.push(line);
  }
  return triangle;
}
pascalsTriangle(6);
Done

The first 19 calls, of 35. This one does not fit on a page.

Step through pascalsTriangle(6) call by call

Explanation

A row is not worked out from scratch; it is read off the row before it. Each number stands under a pair and takes that pair’s total. Only the two ends have a single number above them, so they are the only positions needing a rule of their own.

  1. 1

    row is 0, so the inner loop runs at col 0 only. col === 0 is true, 1 is pushed, and the else branch — the one that reads the row above — is never reached. triangle now has something for the next row to read.

    1
    0

    row=0triangle.length=0

    triangle.push([1])

  2. 2

    row is 1, and both of its positions hit a guard: col === 0 at the left and col === row at the right. Both take 1, so this row is built without opening the one above it either.

    1
    0
    1 1
    1

    row=1triangle.length=1

    triangle.push([1, 1])

  3. 3

    row is 2, and col 1 is the first position that is neither end. above is set to triangle[row - 1], which is [1, 1], and the value pushed is above[0] + above[1].

    1
    0
    1 1
    1
    1 2 1
    2

    row=2above=[1, 1]

    above[0] + above[1] = 1 + 1 → 2

  4. 4

    row is 3 and above is [1, 2, 1]. Position 1 takes above[0] + above[1] = 1 + 2, position 2 takes above[1] + above[2] = 2 + 1. Each position reads the pair it sits between, and the ends take their 1 as always.

    1
    0
    1 1
    1
    1 2 1
    2
    1 3 3 1
    3

    row=3above=[1, 2, 1]

    triangle.push([1, 3, 3, 1])

  5. 5

    row is 4 and above is [1, 3, 3, 1]: 1 + 3, then 3 + 3, then 3 + 1. The 6 in the middle is the only place the two 3s meet.

    1
    0
    1 1
    1
    1 2 1
    2
    1 3 3 1
    3
    1 4 6 4 1
    4

    row=4above=[1, 3, 3, 1]

    triangle.push([1, 4, 6, 4, 1])

  6. 6

    row is 5 and above is [1, 4, 6, 4, 1], giving 5, 10, 10 and 5 between the two 1s. row++ then fails row < n and the six rows are returned.

    1
    0
    1 1
    1
    1 2 1
    2
    1 3 3 1
    3
    1 4 6 4 1
    4
    1 5 10 10 5 1
    5

    row=5above=[1, 4, 6, 4, 1]

    return triangle → 6 rows

More like this

All star & number patterns examples (12) →