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)

Join us at DEV Want to join the conversation?
 

It's easy! Become a DEV member to follow this post, comment, and more.