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] ]

The logic becomes apparent just by looking at the pattern, but the property of pascal’s triangle comes from coefficients in the binomial expansion.
nCk = n-1Ck + n-1Ck-1 and nC0 =1

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        List temp = new LinkedList<Integer>();
        if(numRows==0) return res;
        temp.add(1);
        res.add(temp); 
        if(numRows==1) return res;
        temp = new LinkedList<Integer>();
        temp.add(1); temp.add(1);
        res.add(temp);
        for(int i=3; i<=numRows;i++){
            temp = new LinkedList<Integer>();
            temp.add(1);
            for(int j=0; j<i-2;j++){
                int val = res.get(i-2).get(j) + res.get(i-2).get(j+1);
                temp.add(val);
            }
            temp.add(1);
            res.add(temp);
        }
        return res;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation