Pascal triangle produced for a particular integer K

Question

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(N²)?

---

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

    if(rowIndex>=1){
        toAdd = new ArrayList<Integer>();
        toAdd.add(1);
        toAdd.add(1);
        allList.add(toAdd);
        if(rowIndex==1){
            return toAdd;
        }
    }
    for(int i=1; i<rowIndex; i++){
        ArrayList<Integer> temp = new ArrayList<Integer>();
        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);
}

Answer 1

Types

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

... but, you are not using the more general List<Integer> value, but instead the ArrayList<Integer>. 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 < 0) {
    throw new IllegalArgumentException("Nevative row");
}
if(rowIndex==0){
    toAdd.add(1);
    return toAdd;
}

toAdd = new ArrayList<Integer>();
toAdd.add(1);
toAdd.add(1);
allList.add(toAdd);
if(rowIndex==1){
    return toAdd;
}

Conclusion

I agree that the complexity is about O(n²), 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;
}

Answer 2

Here is an alternative design:

Write a function that takes a row and returns the next row, and then call this function k times:

private ArrayList<Integer> getNextRow(ArrayList<Integer> currRow)
{
    ArrayList<Integer> nextRow = new ArrayList<Integer>();
    nextRow.add(1);
    for (int i=0; i<currRow.size()-1; i++)
        nextRow.add(currRow.get(i)+currRow.get(i+1));
    nextRow.add(1);
    return nextRow;
}

public ArrayList<Integer> getRow(int rowIndex)
{
    ArrayList<Integer> row = new ArrayList<Integer>();
    row.add(1);
    for (int i=0; i<rowIndex; i++)
        row = getNextRow(row);
    return row;
}