loading...

Leetcode - Pascal's Triangle (with JavaScript)

urfan profile image Urfan Guliyev ・2 min read

Today I am going to show how to solve the Pascal's Triangle algorithm problem.

Here is the problem:
Alt Text

Before solving the problem, we should understand how Pascal's Triangle works:

  • Pascal's Triangle starts with "1" at the top, then continues placing numbers below it in a triangular pattern.
  • Each number is the sum of the two numbers directly above it.
  • The first and last row elements are always 1.

Alt Text

Now let’s start to solve the problem

1) First I wrote the base case. If a user requests zero rows, they get zero rows.

var generate = function(numRows) {
    var triangle = [];

//First base case
    if(numRows == 0) { 
        return triangle
    }
}

2) Next, I iterate numRows times using for loop to build Pascal's Triangle. Then I add the second base case -> the first row of the triangle and the first element of all rows are always 1.

var generate = function(numRows) {
    var triangle = [];

//First base case
    if(numRows == 0) { 
        return triangle
    }

    for (var i = 0; i < numRows; i++) {

        triangle[i] = [];
 //Second base case
        triangle[i][0] = 1;
    }
}

3) While I iterate the rows, I also use the second loop to build the elements of each row. Each triangle element (other than the first and last of each row) is equal to the sum of the elements above-and-to-the-left and above-and-to-the-right.

var generate = function(numRows) {
    var triangle = [];

//First base case
    if(numRows == 0) { 
        return triangle
    }

    for (var i = 0; i < numRows; i++) {

        triangle[i] = [];
//Second base case
        triangle[i][0] = 1;

        for (var j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
        }
//The last element of all rows are always 1.
        triangle[i][i] = 1;
    }

    return triangle;
}

Posted on by:

urfan profile

Urfan Guliyev

@urfan

Love coding, eating and travelling

Discussion

markdown guide