Solving Pascal's Triangle in JavaScript

Today's algorithm is to solve Pascal's Triangle:

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

Pascal's Triangle is a triangle that starts with a 1 at the top, and has 1's on the left and right edges. Each element is the sum of the two numbers above it.

In this algorithm, if you're given the number 6, your function should output
[
[ 1 ],
[ 1, 1 ],
[ 1, 2, 1 ],
[ 1, 3, 3, 1 ],
[ 1, 4, 6, 4, 1 ],
[ 1, 5, 10, 10, 5, 1 ]
], which would also be drawn out as

In this post, I'll discuss how to approach this problem, and then go over the solution using JavaScript.

Approaching the Pascal Triangle Problem

In Pascal's Triangle, the first and last item in each row is 1. Each of the inner numbers is the sum of two numbers in a row above: the value in the same column, and the value in the previous column.

One way to approach this problem is by having nested for loops: one which goes through each row, and one which goes through each column. If we're in the first column, we can add 1 to the row. For the subsequent columns, we can add the two values from the above row. If we're in the last column of the row, we can add 1 to the row. We know we're in the last column because the number of columns in each row is equal to the row that we're on--in other words, it's an equilateral triangle.

Coding the Solution

To start coding the solution, we can account for two test cases; if the number of rows in the triangle is 0, then we can automatically return an empty array, []. If the number of rows is 1, then we can return a two-dimensional array with one row and one column, [[1]].

function pascals(numRows) {
    if (numRows === 0) return [];
    if (numRows === 1) return [[1]];
    //...
}

We can initialize an array called result, which we'll return at the end of algorithm--so we can include that return statement now.

We also can set up the first for loop. The outer for loop will account for each row, so it'll increment from 1 until it equals numRows.

function pascals(numRows) {
    if (numRows === 0) return [];
    if (numRows === 1) return [[1]];
    let result = [];
    for (let row = 1; row <= numRows; row++) {
        //...
    }
    return result;
}

Inside the loop, we'll initialize an array called arr. arr will store the value of each row we're in, and will end up getting pushed to the result array.

function pascals(numRows) {
    if (numRows === 0) return [];
    if (numRows === 1) return [[1]];
    let result = [];
    for (let row = 1; row <= numRows; row++) {
        let arr = [];
        //...
        result.push(arr);
    }
    return result;
}

We also need to set up an inner for loop. The inner for loop will keep track of the column we're on, so it'll increment from 0 until it reaches the value of row. We know to increment to the value of row because we're building an equilateral triangle, which means the number row we're on equals the number of columns in that row.

Inside the inner for loop, we want to check if we're in the first or last column. So if col equals 0, or col equals row - 1, then we want to push 1 into arr.

function pascals(numRows) {
    if (numRows === 0) return [];
    if (numRows === 1) return [[1]];
    let result = [];
    for (let row = 1; row <= numRows; row++) {
        let arr = [];
        for (let col = 0; col < row; col++) {
            if (col === 0 || col === row - 1) {
                arr.push(1);
            }
            //...
        }
        result.push(arr);
    }
    return result;
}

Finally, for all of the other columns, we want to push the sum of two values to arr. The first value is the element in the array that's one column to the left, and two rows up. The second value is the element in the array that's in the same column, and two rows up.

The reason we're checking for the element that's two rows up is that we start incrementing the outer for loop at 1, but the result array is 0-indexed.

function pascals(numRows) {
    if (numRows === 0) return [];
    if (numRows === 1) return [[1]];
    let result = [];
    for (let row = 1; row <= numRows; row++) {
        let arr = [];
        for (let col = 0; col < row; col++) {
            if (col === 0 || col === row - 1) {
                arr.push(1);
            } else {
                arr.push((result[row-2][col-1] + result[row-2][col]));
            }
        }
        result.push(arr);
    }
    return result;
}

Let me know in the comments if you have other solutions or any questions!

Comments

[Chety]

Hi,
How about recursion? Below I am sharing my version

function pascalTriangle(level){
    if(level === 0){
        return [[1]]
    }
    const previousValue = pascalTriangle(level - 1); 
    const lastValOfPrevious =   previousValue[previousValue.length - 1]
    const currentValue =  lastValOfPrevious.reduce((acc,num,i) => {
        if(lastValOfPrevious[i + 1] != undefined){
            acc.push(lastValOfPrevious[i] + lastValOfPrevious[i + 1])
        }else{
            acc.push(1)
        }
        return acc;
    },[1]);
    const result = [...previousValue,currentValue]
    return result
}

[Petr Mašát]

It is nice, but I don't prefer "let" and "for" in javascript, so i tried re-writte it

or with JEST testing and doc in gitlab.com/pemasat/playground/-/bl...

I hope that you will like it.

[JEYSSON ALY CONTRERAS]

I rewrite it in a simplest way

function pascal(rows) {
  if (rows === 1) {
    return [[1]];
  }
if (rows === 0) {
    return [];
  }
  const prev = pascal(rows - 1);
  const last = prev[prev.length - 1];
  const next = [1];
  for (let i = 0; i < last.length - 1; i++) {
    next.push(last[i] + last[i + 1]);
  }
  next.push(1);
  prev.push(next);
  return prev;
}