Thursday, January 1, 2015

Pascal's Triangle II (LeetCode Array)

Question: 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?

Idea: Pascal triangle is a problem taught in middle school. So I think it is OK to use the generation equation.
The n'th row: [combination(n, 0), combination(n, 1), combination(n, 2),..., combination(n, n)], where combination(n, k+1) = combination(n, k)*(n-k)/(k+1).

Time: O(n) Space: O(1)

Code:
 public class Solution {  
 public List<Integer> getRow(int rowIndex) {  
     List<Integer> result=new ArrayList<Integer>();  
     long value=1;  
     for(int k=0;k<=rowIndex;k++)  
     {  
       result.add((int)value);  
       value=value*(rowIndex-k)/(k+1);  
     }  
     return result;  
   }  
 }  

No comments:

Post a Comment