Wednesday, June 11, 2014

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

Solution:

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> actualRow = new ArrayList<Integer>();
         actualRow.add(1);
       
        for(int row=0; row<rowIndex; row++)
        {
            List<Integer> previousRow = actualRow;
            actualRow = new ArrayList<Integer>();
            actualRow.add(1);
            for(int i=1; i< previousRow.size(); i++)
            {
                actualRow.add(previousRow.get(i-1) + previousRow.get(i));
            }
            actualRow.add(1);
        }
        return actualRow;
    }
}

No comments :

Post a Comment