LeetCode: Pascal's Triangle II

Totally like Pascal's Triangle problem, just change the return.
n is the number of rows
Time: O(n*n)      Space: O(n*n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: vector<int> getRow(int rowIndex) { vector<vector<int>> result(rowIndex+1); vector<int> row; for(int i=0; i<rowIndex+1; i++) { vector<int> row; for(int j=0; j<i+1; j++){ if(j==0 || j==i) { row.push_back(1); continue; } row.push_back(result[i-1][j-1]+result[i-1][j]); } result[i]=row; } return result.back(); //when no element exist, the program will keep running, } };

Optimization:
To minimize the space complexity to O(2*n), use a vector to store the row above the current row.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: vector<int> getRow(int rowIndex) { vector<int> row_pre; for(int i=0; i < rowIndex+1; i++) { vector<int> row; for(int j=0; j < i+1; j++){ if(j==0 || j==i) { row.push_back(1); continue; } row.push_back(row_pre[j-1]+row_pre[j]); } row_pre=row; } return row_pre; } };

Optimization 2:
With just one vector. Note the for loop condition.

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution { public: vector<int> getRow(int rowIndex) { vector<int> row; for(int i=0; i < rowIndex+1; i++) { for(int j=i-1; j >0 ; j--){ // NOTE: only add (i-1) times row[j]=row[j-1]+row[j]; } row.push_back(1); } return row; } };

Optimization 3:
With math formula. No interest.

reference:
http://fisherlei.blogspot.com/2012/12/leetcode-pascals-triangle-ii.html
http://yucoding.blogspot.com/2013/04/leetcode-question-65-pascals-triangle-ii.html