Today I am going to show how to solve the Pascal's Triangle algorithm problem.
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.
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;
}
Top comments (0)