[LeetCode Road] Pascal's Triangle - Solution/C++

118. Pascal's Triangle

Question:

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

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

Source code

Version 1

Idea:
The last element of vector(row) is always consistent(equals to 1), We add 1 into vector for each rows at 17-18 line.
The first element of vector is also the same, so the index of j is from 1 to i - 1(i is represented the number of numRows). At the range of j, we should add previous value into the current index of value.

At 11 line, prev variable means the first element of vector.
At 13 line, declare temp variable and store row[j] as the next prev.
At 14 line, add prev into row[j].
At 15 line, pass temp to prev.
Finally, we use two loops to implement Pascals's Triangle easily.

Time complexity: O(n²)
Space complexity: O(n²) // O(n*(n+1)/2)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if(numRows < 1) return res;
        
        vector<int> row(1,1);
        res.push_back(row);
        
        for(int i = 2; i <= numRows; i++){
            int prev = 1;
            for(int j = 1; j < i - 1; j++){
                int temp = row[j];
                row[j] += prev;
                prev = temp;
            }
            row.push_back(1);
            res.push_back(row);
        }
        return res;
    }
};