Saturday, January 10, 2015

LeetCode 119: Pascal's Triangle II

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?
public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new LinkedList<>();
        
        for (int i = 0; i <= rowIndex; i++)
        {
            List<Integer> row = new LinkedList<>();
            
            for (int j = 0; j <= i; j++)
            {
                if (j==0 || j==i)
                    row.add(1);
                else if (!result.isEmpty())
                {
                    int first = result.get(j-1);
                    int second = result.get(j);
                    row.add(first+second);
                }
            }
            
            result.clear();
            
            for (int num : row)
                result.add(num);
        }
        
        return result;        
    }
}

No comments:

Post a Comment