Solving Pascal’s Triangle Problem in JavaScript
Hi coders,
We will be solving the famous Pascal’s triangle problem today in JavaScript ES6. Let’s understand the problem first:
Pascal’s triangle is a number triangle with numbers arranged in staggered rows such that it 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
So if you are given to print 7 rows of pascals triangle, this should be your output:
[
[ 1 ],
[ 1, 1 ],
[ 1, 2, 1 ],
[ 1, 3, 3, 1 ],
[ 1, 4, 6, 4, 1 ],
[ 1, 5, 10, 10, 5, 1 ],
[ 1, 6, 15, 20, 15, 6, 1 ]
]
Which can be represented in pictorial form like this:
Approach:
We will be using the brute-force approach to solve this problem here. Now, the first and the last element of the all the column are going to be 1. All the other inner elements will be : (element in the same column + element in the previous column) of the row above it.
We can have two loops, one for the row and the other for the column. For the first column of each row, the element will be 1, for the subsequent columns we will be using two values from the above row such that one value is from the same column and the second one is from the previous column and by adding the two values together we get our element. For the last column again the element will be 1. The number of columns in each row will always be equal to the row itself, e.g. for third row the number of columns will be three. Let’s start coding now.
Solution:
Let’s first create a function which takes an integer numOfRows
as its parameter and returns the array result
containing values for pascal’s triangle.
const pascalsTriangle = (numOfRows) =>{
const result = [];
//...
//...
//...
//...
return result;
}
Now, we have two cases which will have different outputs, numOfRows = 0
and numOfRows=1
, for the first case, we will return an empty array as there will not be any elements. And for the second case, i.e. numOfRows =1
, we will return [[1]]
as the first row of Pascal’s triangle contains only one element, 1.
const pascalsTriangle = (numOfRows) =>{
const result = [];
if(numOfRows === 0) return [];
if(numOfRows === 1) return [[1]];
//...
//...
//...
return result;
}
Let’s now create our first loop, which will be accountable for the number of rows in the pascal’s triangle. The variable of the loop will increment by 1 after every execution, and the loop will run until the variable is equal to the numOfRows
.
const pascalsTriangle = (numOfRows) =>{
const result = [];
if(numOfRows === 0) return [];
if(numOfRows === 1) return [[1]];
for(let row = 1; row <= numOfRows; row++){
//...
//...
//...
}
return result;
}
Now let’s declare a temporary array inside our first loop, which will store the elements present in each column of a row. And we will be pushing this temporary array into our result array after the completion of every execution of the loop.
const pascalsTriangle = (numOfRows) =>{
const result = [];
if(numOfRows === 0) return [];
if(numOfRows === 1) return [[1]];
for(let row = 1; row <= numOfRows; row++){
let tempArray = [];
//...
//...
result.push(tempArray);
}
return result;
}
We can now create the second loop inside the first loop, which will be accountable for each column of a row. The loop will start from zero and will run until it reaches the value of the row.
const pascalsTriangle = (numOfRows) =>{
const result = [];
if(numOfRows === 0) return [];
if(numOfRows === 1) return [[1]];
for(let row = 1; row <= numOfRows; row++){
let tempArray = [];
for(let col = 0; col < row; col++){
//...
//...
}
result.push(tempArray);
}
return result;
}
As, we know that the first column and the last column of the row will always have the same element that is 1, let's handle this case.
const pascalsTriangle = (numOfRows) =>{
const result = [];
if(numOfRows === 0) return [];
if(numOfRows === 1) return [[1]];
for(let row = 1; row <= numOfRows; row++){
let tempArray = [];
for(let col = 0; col < row; col++){
if(col === 0 || col === row - 1){
tempArray.push(1)
}
//...
}
result.push(tempArray);
}
return result;
}
For all the columns falling between the first and the last, we will be using this formula :
tempArray[col] = (result [row-2][col-1] + result[row-2][col])
In the above formula, we are taking two values from the row above the current row, first value is from the same column and second value is from the column-1, we are then adding the two values to get the value of the existing column.
Why row-2
? We have started our first loop, which is loop for the row from 1, and index of the array starts from 0, so if we are inside the second loop which is the loop for columns, and if we want to access the element from the previous row we will have to subtract 2 from the row. Let’s convert it into code.
const pascalsTriangle = (numOfRows) =>{
const result = [];
if(numOfRows === 0) return [];
if(numOfRows === 1) return [[1]];
for(let row = 1; row <= numOfRows; row++){
let tempArray = [];
for(let col = 0; col < row; col++){
if(col === 0 || col === row - 1){
tempArray.push(1)
}
else{
tempArray.push((result [row-2][col-1] + result[row-2][col]));
}
}
result.push(tempArray);
}
return result;
}
That’s it! That’s the final code! Let me know if it helped you in the comment section, also let me know how would you like to solve this problem.
Thank you so much for coming here!
Edited : solution with lesser number of lines https://replit.com/@ajshivali/Pascals-triangle?v=1