DEV Community

Mayank Arora
Mayank Arora

Posted on

118. Pascal's Triangle [Leetcode][C++]

All suggestions are welcome. Please upvote if you like it. Thank you.


Leetcode Problem Link: 118. Pascal's Triangle


Brute Force Solution:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
    // Brute Force Solution Time O(N^2) & Auxiliary Space O(1)
    vector<vector<int>> ret(numRows);
    for (int i = 0; i < numRows; i++) {
    ret[i].resize(i+1); // Resize number of elements in each row from from numRows to i+1 
        ret[i][0]=1; ret[i][i]=1; // Put 1's at first & last element of each row
    for (int j = 1; j < i; j++) {
        // Assigning element values in row from second element to second last element
        // by adding corresponding jth & (j-1)th element in previous row
        // as shown in question animation
        ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
    }
    }
    return ret;
}
};

Enter fullscreen mode Exit fullscreen mode

All suggestions are welcome. Please upvote if you like it. Thank you.

Top comments (0)