Pascal's Triangle

Problem

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:

Solution Approach

Expected Time complexity: $O(n^2)$

Click - to see solution code

C++

class Solution {
   public:
    vector<vector<int>> generate(int n) {
        vector<vector<int>> ans;
        vector<int> a, b;
        a = {1};
        ans.push_back(a);
        if (n == 1) return ans;
        for (int i = 2; i <= n; i++) {
            b.push_back(1);
            for (int k = 0; k < a.size() - 1; k++) {
                b.push_back(a[k] + a[k + 1]);
            }
            b.push_back(1);
            ans.push_back(b);
            a = b;
            b.clear();
        }
        return ans;
    }
};