119. Pascal's Triangle II
1. Description
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:
2. Example
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]
3. Constraints
- 0 <= rowIndex <= 33
4. Follow Up
- Could you optimize your algorithm to use only O(rowIndex) extra space?
5. Solutions
My Accepted Solution(Follow Up)
n = rowIndex
Time complexity: O(n)
Space complexity: O(n)
// when we calculate one row in the Pascal's triangle, we only need the last row
// so we just need to use two rows' space
// further more, we actually just need one row, we could calculate a row from back to front
// so we could just a single row's space
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1);
row[0] = 1;
for (int i = 1; i <= rowIndex; ++i) {
for (int j = i; j > 0; --j) {
row[j] += row[j - 1];
}
}
return row;
}
};