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:
- the value we are processing right now (the value
1
)
- the column above the us (contains the values
[1]
)
- the row we have processed so far (contains the values
[1, 1, 1]
)
- 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:
- the value at this point
- plus the sum of all values above-left of us
- plus the sum of all values above us
- 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.
So, I have an array [n][n], which contains integers. I want to create a new array of the same size
... I only see one array... are you building the array at the same times as adding it up? \$\endgroup\$