Pascal's Triangle I & II

I write about this problem only to clarify how to use ArrayList correctly. ArrayList has a constructor:

public ArrayList(int initialCapacity)

Constructs an empty list with the specified initial capacity.

Parameters:

initialCapacity - the initial capacity of the list

Throws:

IllegalArgumentException - if the specified initial capacity is negative

I thought at first that it can create a list with size of "initialCapacity", apparently that is not the case. It still creates an empty array. However, the "initialCapacity" is the initial capacity of the backing array of the list:

 public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

So the correct way is to create a list and add as many elements as the desired size, then use the set() method to modify the list.

Back to these two problem. The current level of the Pascal's Triangle can be generated from the previous level. So start with the first level, which is 1, we can generate the desired number of rows.

Pascal's Triangle I

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

public List> generate(int numRows) {
        List> rst = new ArrayList> ();
        if (numRows <= 0)
            return rst;
        for (int i = 1; i <= numRows; i++) {
            List curr = new ArrayList ();
            for (int j = 0; j < i; j++) 
                curr.add(-1);
            curr.set(0, 1);
            curr.set(i - 1, 1);
            if (i == 1)
                rst.add(curr);
            else {
                for (int j = 1; j < i - 1; j++) {
                    int n = rst.get(rst.size() - 1).get(j - 1) + rst.get(rst.size() - 1).get(j);
                    curr.set(j, n);
                }
                rst.add(curr);
            }
        }
        return rst;
    }

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 List getRow(int rowIndex) {
        List rst = new ArrayList ();
        if (rowIndex < 0)
            return rst;
        rst.add(1);
        if (rowIndex == 0)
            return rst;
        List prev = new ArrayList(rst);
        for (int i = 1; i <= rowIndex; i++) {
            rst = new ArrayList();
            for (int j = 0; j < i + 1; j++) {
                rst.add(-1);
            }
            rst.set(0, 1);
            rst.set(i, 1);
            for (int j = 1; j < i; j++) {
                int n = prev.get(j - 1) + prev.get(j);
                rst.set(j, n);
            }
            prev = new ArrayList(rst);
        } 
        return rst;
    }