Published in

Nerd For Tech

# Pascal’s Triangle

(LeetCode Easy)

Given an integer `numRows`, return the first numRows of Pascal's triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

`Input: numRows = 5Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]`

Example 2:

`Input: numRows = 1Output: [[1]]`

Constraints:

• `1 <= numRows <= 30`
`class Solution {public:    vector<vector<int>> generate(int numRows) {        vector<vector<int>>r(numRows);                for(int i=0 ; i<numRows ; i++)        {            r[i].resize(i+1);            r[i][0] = r[i][i] = 1;                        for(int j=1 ; j<i ; j++)                r[i][j] = r[i-1][j-1] + r[i-1][j];        }        return r;    }};`

The code is given above as follows. The main intuition behind this logic is that arr[i][j] = arr[i-1][j-1] + arr[i-1][j] , which means the element is the sum of the element on top of it and the element besides the top of it. Let me explain it through an example :

See how the pattern follows and also we see that the starting and the ending element is 1 which is true for all rows.

Now let us dry run the above code :

`i =0, r[0].resize(1) ie. the first row will have 1 elementr[0][0] = 1Output : [[1]]Now , i = 1, and j = 1r[1][0] = r[1][1] = 1Output : [[1],[1,1]]i = 2r[2][0] = r[2][2] = 1i = 2, j = 1r[2][1] = r[1][0] + r[1][1] = 1 + 1 = 2Output : [[1],[1,1],[1,2,1]]i = 3r[3][0] = r[3][3] = 1i = 3, j = 1r[3][1] = r[2][0] + r[2][1] = 1 + 2 = 3i = 3, j = 2r[3][2] = r[2][1] + r[2][2] = 2 + 1 = 3Output : [[1],[1,1],[1,2,1],[1,3,3,1]]i = 4r[4][0] = r[4][4] = 1i = 4 , j = 1r[4][1] = r[3][0] + r[3][1] = 1 + 3 = 4i = 4, j = 2 r[4][2] = r[3][1] + r[3][2] = 3 + 3 = 6i = 4 , j = 3r[4][3] = r[3][2] + r[3]][3] = 3 + 1 = 4Output : [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]Time Complexity - O(n)Space Complexity - O(1)`

Hope this helps! Till then keep coding!!

Stay tuned & subscribe for more!!!💻🙌 Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati

--

--

## More from Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

## Sukanya Bharati

152 Followers

A happy , motivated & a curious soul if you end up finding me 😎😁.