loading...

Solving Pascal's Triangle in JavaScript

alisabaj profile image Alisa Bajramovic ・4 min read

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.

Five triangles next to each other. The first triangle has 6 hexagons on each side. The left side's hexagons are yellow and have '1' in them. The right side's hexagons are yellow and have '1' in them. The inner hexagons are all blue. The second triangle is the same as the first, except in the third row, the blue hexagon has a '2' in it, with a red arrow pointing at it from the two hexagons above it. The third triangle is the same as the second, but the fourth row has two 3's in the blue hexagons, with red arrows pointing at them from the above hexagons. The fourth triangle is the same as the third, but the fifth row has 4, 6, 4 in blue hexagons, with red arrows pointing at them from above. The final triangle is the same as the fourth, but the last line has 5, 10, 10, 5 in the blue hexagons, with red arrows pointing at each hexagon from the numbers above.

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

A triangle with 6 equal sides. Each element is a hexagon. The left and right sides are yellow hexagons, and all other hexagons are blue. First row: 1. Second row: 1 1. Third row: 1 2 1. Fourth row: 1 3 3 1. Fifth row: 1 4 6 4 1. Sixth row: 1 5 10 10 5 1.

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!

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

pic
Editor guide