Pascal’s Triangle

pretty19

Loveena Saran

Posted on January 31, 2022

Pascal’s Triangle

Deduction made from how the Pascal's triangle is constructed:

The boxes at the start and end of the list are always set to '1'

Pascal Triangle

Initially the first 2 levels do not have any adding up of elements and the process of adding starts from the 3rd level

Pascal Triangle

Adding up the previous level answer leads to the new numbers at the center of the triangle

Pascal Triangle

How to approach this problem?

  • We can keep a pointer to here 'i' for each level of the triangle
  • Also if we notice there are center boxes that grow in triangular pattern. Image description

Notice when level is '1' we have '0' elements to be added from previous levels.
At level 1 --> 0 elements are formed by adding
At level 2 --> 1 elements are formed by adding
At level 3 --> 2 elements are formed by adding
and so on...

  • we can have a 'j' variable that we initialize when we are at 1st level of 'i'.
  • Here we are initializing 'j' to be 'zero' and less than 'i'.

'i' and 'j' values Serve multiple purposes in this problem

  1. 'i' indicates each level and 'j' indicates the elements formed by adding up previous elements.
  2. 'j' runs at a 1 less than 'i' as it starts from '0' and creates boxes at each level.
  3. As the answer is stored in List i.e (List of Lists). We can to retrieve the previous level data and add this to form the current value.

Code:

   for(int i=1; i<=numRows; i++){
            for(int j=0; j<i; j++){
Enter fullscreen mode Exit fullscreen mode
  • For the first and the last box we want to add '1'
for(int i=1;i<=numRows;i++){      
    for(int j=0; j<i; j++){
      if(j==0 || j==i-1){  // add '1' to first box and last box
          curr.add(1);  // Add to list curr
               }
Enter fullscreen mode Exit fullscreen mode

-For boxes at the center ranging from (1:i-1)

for(int i=1;i<=numRows;i++){
           List<Integer> curr = new ArrayList<>();       
           for(int j=0;j<i;j++){
               if(j==0 || j==i-1){
                   curr.add(1);
               }
               else{
curr.add(levels.get(i-1).get(j)+ levels.get(i-1).get(j-1)); // to form new elements by  adding values from previous levels
           }
        }
Enter fullscreen mode Exit fullscreen mode

Dry Run:
Pascal Triangle

Pascal Triangle

Pascal Triangle

Pascal Triangle

Do like if you found this helpful. This would help me learn and create new articles like this.
Thanks!

💖 💪 🙅 🚩
pretty19
Loveena Saran

Posted on January 31, 2022

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Pascal’s Triangle
beginners Pascal’s Triangle

January 31, 2022

Memoization in JavaScript
javascript Memoization in JavaScript

October 10, 2020