Nerd For Tech
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 = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[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 element
r[0][0] = 1
Output : [[1]]
Now , i = 1, and j = 1
r[1][0] = r[1][1] = 1
Output : [[1],[1,1]]
i = 2
r[2][0] = r[2][2] = 1
i = 2, j = 1
r[2][1] = r[1][0] + r[1][1] = 1 + 1 = 2
Output : [[1],[1,1],[1,2,1]]i = 3
r[3][0] = r[3][3] = 1
i = 3, j = 1
r[3][1] = r[2][0] + r[2][1] = 1 + 2 = 3
i = 3, j = 2
r[3][2] = r[2][1] + r[2][2] = 2 + 1 = 3
Output : [[1],[1,1],[1,2,1],[1,3,3,1]]i = 4
r[4][0] = r[4][4] = 1
i = 4 , j = 1
r[4][1] = r[3][0] + r[3][1] = 1 + 3 = 4
i = 4, j = 2
r[4][2] = r[3][1] + r[3][2] = 3 + 3 = 6
i = 4 , j = 3
r[4][3] = r[3][2] + r[3]][3] = 3 + 1 = 4
Output : [[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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sukanya Bharati

Sukanya Bharati

152 Followers

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