[Leetcode 36] 119 Pascal's Triangle II

Problem:

Given an index k, return the k^th 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?

Analysis:

The direct way to solve the problem is to use the formula: C(i, k) = k! / (i! * (k-i)!). But it will exceed the int number range if k is very large.

So we have to use the iterative way to construct the answer: to compute kth row, we first compute (k-1)th row and then use it to construct the desired row.

Code:

 1 class Solution {
 2 public:
 3  vector<int> getRow(int rowIndex) {
 4      vector<int> res;
 5 
 6      res.push_back(1);
 7      if (rowIndex == 0) return res;
 8      res.push_back(1);
 9      if (rowIndex == 1) return res;
10 
11      for (int i=1; i<rowIndex; i++) {
12          vector<int> tmp;
13          tmp.push_back(1);
14          for (int j = 1; j <= i; j++) {
15              tmp.push_back(res[j-1] + res[j]);
16          }
17          tmp.push_back(1);
18 
19          res = tmp;
20      }
21 
22      return res;
23  }
24 
25     
26 };

View Code

Attention:

Notice to add a new element into tmp, use push_back, not [].

The inner loop's max value is i not rowIndex.