119. Pascal's Triangle II

119. Pascal's Triangle II (Easy)

Given a non-negative index k where k ≤ 33, return the k^th index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

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

Follow up:

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

Companies:
Adobe, Google, Amazon

Solution 1.

// OJ: https://leetcode.com/problems/pascals-triangle-ii/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex + 1, 1);
        for (int i = 2; i <= rowIndex; ++i) {
            for (int j = i - 1; j > 0; --j) ans[j] += ans[j - 1];
        }
        return ans;
    }
};