Java IndexOutOfBounds when trying to get a previous entry in a List

Question

I'm working on a question where you are supposed return n rows of pascals triangle given and int n and return it as a List of Lists. However I'm getting an index out of bounds exception when I try to call on a previous row and I'm not exactly sure why.

public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();
        List<Integer> row = new ArrayList<>();
        for(int i = 0; i < numRows; i++){
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    row.add(1);
                }
                else{
                    if(i != 0 && j != 0){
                        int num = triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j);
                        row.add(num);
                    }
                }
            }
            triangle.add(row);
            row.clear();
        }
        return triangle;
    }

I added the if(i != 0 && j != 0) line in hopes of resolving it but the error persists.

Answer 1

Count the amount of new statements being executed.

I count only 2 new statements, both before your loops even begin.

That means there are 2 array lists. Total.

Given that your code is supposed to return a lot more lists than that, how does this work? Well, java is based on references. All non-primitives values are, in fact, references. It's like a page in an address book, not a house. List<Integer> row = new ArrayList<>(); does 2 things:

• It builds a house (that's the new ArrayList<>(); part)
• It writes down the address of this house on a page titled 'row'.
• triangle.add(row) will simply create a copy of the address book page, not of the house. You simply write down the address, then go over to the house, smash everything inside (row.clear()), and start over again. You keep refilling the same house, smashing everything in it. triangle is an address book containing many pages, each page having the same address, all leading to a house where someone has repeatedly filled it up, smashed it all to smithereens.

This gets us back to: Count the new.

Here you epxect a 5-row sierpinski to have a grand total of 6 lists made: 1 list for each row, and then one more as a list of lists. That means I need to 6 'new' statements being executed.

Answer 2

You need to remove row.clear(); you're wiping out the contents of the row you just added to the triangle. The reason you're doing that is you think you can keep adding the same row to the triangle; you need to create a new row for each loop.

Answer 3

You made a mistake on how you were using/reusing a List for row.

You have to create a whole new List for every new row, because otherwise, you'll put the same instance in every row of the trangle and you're adding the very same numbers in every row.

What you did produced a "triangle" like this:

1

11
11

The third row had to get values from the second, but it failed, as you cleared the row (and therefore every rows at the very same time) before calculating the third row.

The following change is needed:

public List<List<Integer>> generate(int numRows) {
  List<List<Integer>> triangle = new ArrayList<List<Integer>>();

  for(int i = 0; i < numRows; i++){
    List<Integer> row = new ArrayList<>();  // <<-- new row instead of clearing it

    ...
  }

  trangle.add(row);
  // row.clear(); // <-- this was the second part of the mistake