# LeetCode Problem: Pascal’s Triangle II

By | 2013 年 1 月 17 日

Follow the algorithm in LeetCode Problem: Pascal’s Triangle, we can simple return the required row from the result.

But, we can optimize this to use constant extra space, even better than the required O(k) extra space in the problem description below.

``` [1,3,3,1],
[1,4,6,4,1]
```

Take the above two rows as example, we can see that, the element in the last row is only relative to the element above it and the one before the element above it. So we can generate the last row from the previous row in backward order in place.Thus, we do not need the extra spaces.

Pascal’s Triangle II Oct 29 ’12
Given an index k, return the kth row of the Pascal’s triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?

Code, 16ms pass large test set

```class Solution {
public:
vector getRow(int rowIndex) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
if(rowIndex < 0) return ret;
for(int ir = 0; ir <= rowIndex; ++ir) {
//put an 1 at the end of this row
ret.push_back(1);
//handle the rest of elements backward
for(int ic = ir - 1; ic > 0; --ic) {
ret[ic] = ret[ic] + ret[ic - 1];
}
}
return ret;
}
};
```