118. Pascal’s Triangle

Question

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.

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

---

Approach

1. Create 2 vectors, one to store a single level of the pascal triangle, one to consolidate all levels.
2. Start from the top row to the bottom, it is known that level 1 will have 1 element, level 2 will have 2 elements etc.
3. The element on the left and right most are always 1.
4. For other elements, it is the sum of the two elements on top (row - 1, index - 1) + (row - 1, index)
5. After each level, push it into the consolidated vector.

Solution

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<int> out;
        vector<vector<int>> finalOut;

        for(int lv = 0; lv < numRows; lv++){
            for(int i = 0; i <= lv; i++){
                if(i == 0 || i == lv) out.push_back(1);
                else out.push_back(finalOut[lv - 1][i - 1] + finalOut[lv - 1][i]);
            }
            finalOut.push_back(out);
            out.clear();
        }
        
        return finalOut;
    }
};