Can any one tell me why line 9 has IndexOutOfBound Exception?


  • 0
    H

    public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows)

     {
            ArrayList<ArrayList<Integer>> pascalTriangle = new ArrayList<ArrayList<Integer>>(numRows);
            for(int n= 0; n < numRows;n++ )
            {
                for(int j=0;j<=n;j++)
                {
                    if(j==0)
                    pascalTriangle.get(n).add(0,new Integer(1));
                    else
                    {
                    pascalTriangle.get(n).add(j, new Integer((pascalTriangle.get(n).get(j-1).intValue())*(n+1-j)/j));    
                    }
                }
                
                
            }
            return pascalTriangle;
        }
    }

  • 0
    M

    When you create an ArrayList, it starts out as size 0, so calling get(0) on it will be out of range. Your calling ArrayList<ArrayList<Integer>>(numRows) gives it an initial capacity of numRows, but that just is how much memory is provided at the start. There are still no items in the list, and so you need to actually create the ArrayLists that will be placed in it.

    public ArrayList<ArrayList<Integer>> generate(int numRows){
        ArrayList<ArrayList<Integer>> pascalTriangle = new ArrayList<ArrayList<Integer>>(numRows);
        for(int n= 0; n < numRows;n++ ){
            ArrayList<Integer> row = new ArrayList<Integer>(n+1);  //create the arraylist of a row
            for(int j=0;j<=n;j++){
                if(j==0)
                    row.add(0,new Integer(1)); //use that arraylist instead of grabbing from pascal
                else{
                    row.add(j, new Integer(row.get(j-1).intValue())*(n+1-j)/j);    
                }
            }
            pascalTriangle.add(row);  //add row to list of rows in triangle
        }
        return pascalTriangle;
    }
    

    }


  • 0
    H

    Thank you so much for pointing out this! I got it passed.


  • 0
    Y

    "When you create an ArrayList, it starts out as size 0." The default size of an ArrayList is 10, instead of 0. So there's no need to indicate the size when creating the ArrayList.
    The calling get(0) on it failed was because Hillian didn't create an ArrayList at all before doing anything on it.


  • 0
    M

    The default capacity is 10, not size. Size refers to how many elements are actually in the ArrayList (starts at 0), while capacity refers to the amount of memory currently provided for it (default at 10, or overwritten to another number as in this example). Once you exceed the capacity, the system needs to allocate more memory for it, but until then adding and removing elements does nothing to it. If you know the maximum number of elements that will be present at a time, you can allocate to that size, and avoid the time needed to allocate more memory when the size tries to exceed the capacity.


  • 0
    Y

    Right, right. I meant capacity. Sry I picked the wrong term. I mean the reason your code works is because of the statement creating a new ArrayList - "ArrayList<Integer> row = new ArrayList<Integer>(n+1)", instead of indicating the initial size. It'll work using "ArrayList<Integer> row = new ArrayList<Integer>()".


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.