Pascal triangle produced for a particular integer K

Please be brutal and let me know what you think of the code below, if written at an interview.

Problem:


Given an index k, return the kth row of the Pascal's triangle.


For example, given k = 3, return [1,3,3,1].


Time it took:

25 minutes (perfectly working solution)


Space Complexity:

O(K)


Time Complexity:

O(N2)?

public ArrayList getRow(int rowIndex) {
    List> allList = new ArrayList>();
    ArrayList toAdd = new ArrayList();
    if(rowIndex==0){
        toAdd.add(1);
        return toAdd;
    }

    if(rowIndex>=1){
        toAdd = new ArrayList();
        toAdd.add(1);
        toAdd.add(1);
        allList.add(toAdd);
        if(rowIndex==1){
            return toAdd;
        }
    }
    for(int i=1; i temp = new ArrayList();
        temp.add(1);
        for(int j=1; j<allList.get(i-1).size(); j++){
            temp.add(allList.get(i-1).get(j-1) + allList.get(i-1).get(j));
        }
        temp.add(1);
        allList.add(temp);
    }
    return allList.get(rowIndex-1);
}

Types

Given the description, I would assume that the return value is supposed to be int[] instead of List....

... but, you are not using the more general List value, but instead the ArrayList. Always use the most general class type for your interfaces.

Also, by keeping the data as Integer values, you are doing a lot of boxing, and unboxing in the loops. Really, you should keep the calculations as Java primitives (int), and then box the results if needed.
Conditions

Your code has a special-case for row 0, where it returns [1]. By preference, I recommend not having special cases, although it is a rule I bend often.

Still, after the rowIndex == 0 special case, you then check to see whether it is rowIndex >= 1. This does not make sense because the rowIndex == 0 case returned from the function, so the other condition is useless. Well, not quite useless, it avoids an error condition for negative values. But, the negative-value condition should have been checked at the method start. Basically, it is a useless check. Consider this restructure:

if (rowIndex ();
toAdd.add(1);
toAdd.add(1);
allList.add(toAdd);
if(rowIndex==1){
    return toAdd;
}

Conclusion

I agree that the complexity is about O(n2), but I know it must be psosible to do it faster. The data types are a problem, but the result looks accurate.
Alternative...

So, I cheated, and looked at wiki, and it has a relatively easy function for calculating the row values for a function. I adapted it here. This is the way I would have done it, if I was able to google the algorithm. I would have used a similar approach to you, but as arrays-of-int instead, if I could not search the algorithm.

public static final int[] pascalRow(final int row) {
    // using same names as wikipedia:
    // http://en.wikipedia.org/wiki/Pascal%27s_triangle#Calculating_a_row_or_diagonal_by_itself
    int n = row + 1;
    int[] ret = new int[n];
    int val = 1;
    final int mid = (n)/2;
    for (int k = 0; k <= mid; k++) {
        ret[k] = val;
        ret[n - 1 - k] = val;
        val = (int)(val * ((n - k - 1) / (double)(k + 1)));
    }
    return ret;
}

StackExchange Code Review Q#46131, answer score: 5