# Pascal's Triangle - LeetCode

The problem is taken from  [118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/).

## Approach
Let's make a pascal's triangle of size 5.

```
1 

1      1

1      2       1

1       3      3       1

1       4      6        4      1
``` 

1. We could see that the very first and the very last element of each row is 1. So we need to calculate only middle ones. 

2. Again, for every intermediate number(say, arr[i][j] ) in a row is sum of arr[i-1][j] and arr[i-1][j-1]. 

This much concept is enough for making a pascal's triangle of any size. 

**Code - **
```
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        
        for(int i=0; i<numRows; i++) {
            vector<int> temp(i+1, 1);
            
            for(int j=1; j<i; j++) {
                temp[j] = ans[i-1][j] + ans[i-1][j-1];
            }
            
            ans.push_back(temp);
        }
        
        return ans;
    }
};
```
## Complexities 
Time complexity - O(n^2). Very obvious because we are working with a 2D array.
Space complexity - O(n^2). Same as above.