loading...

Solving Pascal's Triangle in JavaScript

alisabaj profile image Alisa Bajramovic ・4 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

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

Discussion

markdown guide