DEV Community

Urfan Guliyev
Urfan Guliyev

Posted on

Leetcode - Pascal's Triangle (with JavaScript)

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
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)