5
\$\begingroup\$

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);
}
\$\endgroup\$
5
\$\begingroup\$

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

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.