Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3 Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0 Output: [1]
Example 3:
Input: rowIndex = 1 Output: [1,1]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?
Companies: Amazon, Goldman Sachs, Microsoft, Yahoo
Related Topics:
Array, Dynamic Programming
Similar Questions:
// 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;
}
};