119. Pascal's Triangle II Leetcode Java

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?

Solution:

This is a extension problem of the previous problem: Pascal's Triangle

The difficulty of this problem is to use only O(k) extra space.

We know that res[i][j]=res[i-1][j-1]+res[i-1][j], so if we iterate j from back to front, which will update jth column first and then (j-1)th. This is very important, because when we calculate res[i][j], we need res[i-1][j-1] rather than res[i][j-1]. So in this way, we don't have to use extra space to store res[i-1][j-1]. 

   public List<Integer> getRow(int rowIndex) {  
     List<Integer> res=new ArrayList<Integer>();  
     if(rowIndex<0) return res;  
       res.add(1);  
     for(int i=1;i<=rowIndex;i++){  
       for(int j=i-1;j>=1;j--){  
         res.set(j,res.get(j)+res.get(j-1));  
       }  
      res.add(1);  
     }  
     return res;  
   }  
   }