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


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

• 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. – bazang Apr 3 '14 at 21:38
• @bazang - edited to include an 'revised' version of what I expect. – rolfl Apr 3 '14 at 21:41

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