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.

CodePudding user response：

I see the issue with your code. The problem is that you are trying to access elements in the previous row of the Pascal's triangle before they have been added to the triangle list. In other words, you are trying to access triangle.get(i-1) on the same iteration of the outer loop when i is 0.

One way to fix this issue is to move the inner loop that generates each row of the triangle to a separate function. Then, you can add the first row of the triangle manually and call the function to generate the subsequent rows. This will ensure that the previous rows have been added to the triangle list before you try to access them.

Here is the modified code that should solve the index out of bounds exception:

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

    // Add the first row manually
    triangle.add(Arrays.asList(1));

    // Generate the remaining rows
    for (int i = 1; i < numRows; i  ) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j  ) {
            if (j == 0 || j == i) {
                row.add(1);
            } else {
                int num = triangle.get(i-1).get(j-1)   triangle.get(i-1).get(j);
                row.add(num);
            }
        }
        triangle.add(row);
    }

    return triangle;
}

I hope this helps! Let me know if you have any questions or if you need further clarification.

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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