Pascal's Triangle - LeetCode

The problem is taken from 118. Pascal's 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.