Store values from pyramid in jagged array

Question

Here's my code:

ArrayList<ArrayList<Integer>> nums = new ArrayList<>();
    int index = 0;
    for(int i = 0; i < 15; i++){
        nums.add(new ArrayList<Integer>());
        int j = 0;
        while(!(j > i)){
            if(Character.isDigit(pyramid.charAt(index))){
                String s = "" + pyramid.charAt(index) + pyramid.charAt(index + 1);
                int c = Integer.parseInt(s);
                nums.get(i).add(c);
                j++;
                index++;
            }
            index++;
        }
    }

'Pyramid' is a string that contains a fifteen-row pyramid of numbers (top row has one number, next row has two numbers, etc.). Doing it this way, I get a jagged ArrayList.

My question is how do I accomplish this as an array? The only way I can think to get all of the numbers in their own array is to make an 2D array that is 15 arrays long with 15 spots in each array. Bit of a waste since I won't be using every index of every array (I only use every index with the last one). Any ideas?

Answer 1

If you really want to initialize a 2D jagged array you could do something like this:

 public static void main( String [] args){
   int [][] jaggedArray = new int [15][];
   for (int i=0; i<15; i++){
     jaggedArray[i] = new int[i+1];
 } 

However, in the question it looks like you're checking at runtime if the characters in the string are numbers and adding them dynamically. The problem with ArrayLists vs Arrays is that the former lets you change the size dynamically whereas the latter doesn't. So you either have to:

• Know the static size ahead of time and intialize it the way above
• Go through the string and determine the static size as others have said and then initialize it
• Otherwise, you need to use a data structure that allows for dynamic resizing

Also, I'm not sure of the application, but if you're guaranteed that this thing won't be bigger than 15x15, I wouldn't worry too much about the tiny bit of over-allocation.

Answer 2

You could go through the string twice. The first time, figure out how many array elements you need (looks like you can just count the digits in pyramid, but stop when count reaches i, or something like that). Then do something like arr[i] = new Integer[count];, and go through the string again to set up the elements.

Answer 3

If you have a pyramid of height n you simply need an array of to store it. So if your pyramid has a height of 10 elements you need (10*11/2) 55 elements to store all the values.

So if you want to know where an arbitrary element i is in the pyramid you simply solve equation for n, which gives you:

This equation seems hella stupid, but it's correct.

So the position 3920 in the array is in the pyramid gives us n = 88.04518620455886. We round this down, so 88th row, which began at index 3916 (88*89/2).

3920 - 3916 = 4.

So i=3920 is at the 4th index of 88th row.

pyramidsize(n) = (n * (n + 1)) / 2;

pyramid(r,x) = array[(r*(r+1))/2 + x];

row(i) = (int)Math.floor(Math.sqrt(2*i+0.25d)-0.5d);

indexinrow = pyramidsize(row(i)) - i;

Though, most of the time you'll just be iterating the pyramid rather than looking up the pyramid to array conversions, which means you can really just add them to an arraylist or predefine an array (based on the needed size) and cycle through them, but you can just store them all in the array and lookup the exact needed position with a little bit of calculation.