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

118. Pascal's Triangle II

Question:

Given an integer rowIndex, return the rowIndex^th row of the Pascal's triangle. Notice that the row index starts from 0. In Pascal's triangle, each number is the sum of the two numbers directly above it.

Follow up: Could you optimize your algorithm to use only O(k) extra space?

Example:

Input: rowIndex = 3
Output: [1,3,3,1]

Input: rowIndex = 0
Output: [1]

Constraints:
0 <= rowIndex <= 33

Source code

Version 1

Idea:
It is familiar with Pascal's Trangle question, you can use similar algorithm to implement it.
However, the efficiency of algorithm is not optimization.

Time complexity: O(rowIndex²)
Space complexity: O(rowIndex) // <- O(rowIndexx + 1>

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res(1,1);
        if(rowIndex == 0) return res;
        
        for(int i = 1; i <= rowIndex; i++){
            int prev = 1;
            for(int j = 1; j < i; j++){
                int temp = res[j];
                res[j] += prev;
                prev = temp;
            } 
            res.push_back(1);
        }
        return res;
    }
};

Version 2

Idea:
Here's the best algorithm.
At first, declare a vector that consists rowIndex + 1 elements. Must be add 1, because row index starts from 0. So the size of vector is ready, we don't use push_back() in loop anymore.

Whatever a value of rowIndex is, the first position of vector is always 1, so we pass 1 to res vector.
At 9 line, we calculate each elements in reverse(it not includes the frist element).

E.g., Input: rowIndex = 2
i = 1, res=[1, 0, 0]
i = 1, res=[1, 0 + 1, 0] = [1, 1, 0]
i = 2, res=[1, 1 + 1, 0 + 1] = [1, 2, 1] (output)

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> res(rowIndex+1);
        res[0] = 1;
        
        for(int i = 1; i <= rowIndex; i++){
            for(int j = i; j > 0; j--)
                res[j] += res[j-1];
        }
        return res;
    }
};