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;
}

• bazang: I don't understand what you mean by the under condition is useless. If rowIndex is 0, then my function returns end of story. As far as the [x, x,x]values going, that's just how the problem describes it, the return value is supposed to be a List; so that's not an issue. Thank you for your time as always.
• rolfl: @bazang - edited to include an 'revised' version of what I expect.

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;
}