Sunday, February 9, 2014

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution:
Basic implementation question.

public class Solution {
    public ArrayList> generate(int numRows) {
        ArrayList> results = new ArrayList>();
        
        if(numRows <= 0) return results;
        
        ArrayList firstRowResult = new ArrayList();
        firstRowResult.add(1);
        results.add(firstRowResult);
        if(numRows == 1) return results;
        
        ArrayList prevRowResult = new ArrayList();
        prevRowResult.add(1);
        prevRowResult.add(1);
        results.add(prevRowResult);
        if(numRows == 2) return results;
        
        for(int row=3; row<=numRows; row++){
            ArrayList rowResult = new ArrayList();
            rowResult.add(1);
            for(int col=1; col<=row-2; col++){
                int temp = prevRowResult.get(col) + prevRowResult.get(col-1);
                rowResult.add(temp);
            }
            rowResult.add(1);
            results.add(rowResult);
            prevRowResult = rowResult;
        }
        return results;
    }
}

No comments:

Post a Comment