# 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] = 1Output : [[1]]Now , i = 1, and j = 1

r[1][0] = r[1][1] = 1Output : [[1],[1,1]]i = 2

r[2][0] = r[2][2] = 1i = 2, j = 1

r[2][1] = r[1][0] + r[1][1] = 1 + 1 = 2Output : [[1],[1,1],[1,2,1]]i = 3

r[3][0] = r[3][3] = 1i = 3, j = 1

r[3][1] = r[2][0] + r[2][1] = 1 + 2 = 3i = 3, j = 2

r[3][2] = r[2][1] + r[2][2] = 2 + 1 = 3Output : [[1],[1,1],[1,2,1],[1,3,3,1]]i = 4

r[4][0] = r[4][4] = 1i = 4 , j = 1

r[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 = 3

r[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 ☕