Pascal's Triangle

We will discuss Pascal's Triangle which is a LeetCode question.

 

Related LeetCode questions : Similar Questions

 

Approach : 

1. First we will create vector with size 1 & value 1 in it. This 1 will be value of 1st row.

vector<vector<int>> triangle(numRows, vector<int> (1,1));   

     

2. Then we will simply run two nested loop. Same as we would have done while creating triangle like structure.

3. On every iteration we will store previous row in a vector.

4. Then simply we will add previous row elements & compute further element.

5. At last we will push 1 in the vector & return the vector. 

Solution

 

Next we will discuss variant of this question which is Pascal's Triangle II

This is similar to the one discussed above. The only difference is that we are running our loop in backward direction. The reason to move the loop in backward direction is :

 

Remember that you're overwriting the current index with (the value in the current index + the value in the index to the left of it) If you go left to right, you change the value in the current index & move to the right, but when you try to base it off of the index to the left of it (as mentioned above), that ends up being the index you just changed. Going right to left ensures you're not taking into account any numbers you just changed. Try going left to right & using a row index of . You get [1, 3, 4, 1] instead of [1, 3, 3, 1] because of this.

 

Solution

 

Other articles : Development related, Competitive Coding