Partial sums of two dimensional array

Question

I recieve a number n and then recieve n*n integers, representing a matrix, or an array of [n][n]. I want to create an array [n][n], where every cell contains the sum of all cells "left and above" from the original array, while not creating the array, just using the values. For example, the cell [5][7], will contain the sum of the block [0][0] to [5][7] out of the original array.

I seriously need to simplify or speed up my code.

void read() {
    size = scan.nextInt();
    arrayLoad();
}

void arrayLoad() {
    area_values = new int [size][size];
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            add(scan.nextInt(),i,j);
        }
    }
}

void add(int num, int x, int y) {
    for (int i = x; i < size; i++) {
        for (int j = y; j < size; j++) {
            area_values[i][j] += num;
        }
    }
}

This is O(n^4), which, as you may be able to tell, is not exactly easy for n 4+ digits.

Answer 1

This is an interesting problem. I think your solution will be possible and much, much faster if you use memoization. This is the process where you remember your previous calculations and reuse them in your current calculations.

So, for example, suppose you process your array row-by-row.... if your input 2D array is:

1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

And we were now processing the second row, and fourth column, our current result would look like (our current position is marked with a ?):

1 2 3 4 5 6 7
2 4 6 ? 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Now, at that position, we know that the value will be 8 because we are human, and can see that. The best algorithm on the computer though, to get that 8, is that we can split the data we know in to 4 areas....

Consider the input data again (I have marked our spot with the parenthesis):

1 1 1 1 1 1 1
1 1 1(1)1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

The 4 areas that we can think of as special are:

1. the value we are processing right now (the value 1)
2. the column above the us (contains the values [1])
3. the row we have processed so far (contains the values [1, 1, 1])
4. the rectangle above-left of where we are so far (contains the value [1, 1, 1] as well)

Now, what is the sum of the values in the rectangle? We know that, because we have our grid right now which looks like:

1 2(3)4 5 6 7
2 4 6 ? 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

So, the rectangle from (0,0) to (0,2) has the sum 3 which has already been calculated (and which I have marked with parenthesis).

We have also calculated the sum of the data in the row to the left of us... look at the grid again:

1 2(3)4 5 6 7
2 4(6)? 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

The sum of the values in the row to the left is the difference between the rectangle above left, and the rectangle plain-left, or 6 - 3 == 3.

Similarly, the sum of the values in the column above us, is the sum of the rectangle above us, less the rectangle above-left of us.

So, for any position in the solution matrix, the solution-sum of the values is:

1. the value at this point
2. plus the sum of all values above-left of us
3. plus the sum of all values above us
4. plus the sum of all values to the left.

Using a more convenient input format than the scanner, this can all be done in a single loop....

int[][] sumAboveLeft(int[] datasource) {
    if (datasource == null || datasource.length == 0 || datasource.length != datasource[0] * datasource[0] + 1) {
        throw new IllegalArgumentException();
    }
    // first value in the source data is the matriz size
    final int size = datasource[0];
    // because the first value is the size, we expect the loop limit to be unusual.
    final int limit = datasource.length - 1;

    int[][] result = new int[size][size];

    for (int i = 0; i < limit; i++) {
        // convert the linnear/flat address to a row/column
        int row = i / size;
        int col = i % size;

        // rectangle-sum above us
        int abovesum = row > 0 ? result[row - 1][col] : 0;
        // rectangle-sum to left of us
        int leftsum = col > 0 ? result[row][col - 1] : 0;
        // rectangle-sum above-left of us.
        int aboveleftsum = (col > 0 && row > 0) ? result[row - 1][col - 1] : 0;
        // our value at this point (note the index+1 offset because the first value is the size)
        int val = datasource[i + 1];
        // the sum here is
        // the value here
        // plus above-left-rectangle-sum
        // plus above-column-sum
        // plus left-row-sum
        result[row][col] = val
                         + aboveleftsum
                         + (leftsum - aboveleftsum)
                         + (abovesum - aboveleftsum);
    }
    return result;

}

I have put a lot of comments in there for you...

I have also tested it with:

public static void main(String[] args) {
    System.out.println(Arrays.deepToString(sumAboveLeft(new int[]{
         7,
         1, 1, 1, 1, 1, 1, 1,
         1, 1, 1, 1, 1, 1, 1,
         1, 1, 1, 1, 1, 1, 1,
         1, 1, 1, 1, 1, 1, 1,
         1, 1, 1, 1, 1, 1, 1,
         1, 1, 1, 1, 1, 1, 1,
         1, 1, 1, 1, 1, 1, 1,
    })));
}

So, the process can be done in O(n), where n is the number of members in the matrix.