# I’m looking for faster way for looping through 2 2d arrays than 4 for loops

I have to count what’s the biggest count of “1” in a square from a bigger square made of “1” and “0”, like:

```{0111101010}
{1000010110}
{1001001000}
{1110011001}
{1111110010}
{0011110000}
{0001101000}
{0001101010}
{0110101101}
{0001000001}
```

Each 0 and 1 is also an element of the array, and let’s say I have to find the most “1” in a 6 elements side square. I came up with something like this (smallSquareSize = 6):

```for (int i = 0; i < tab.length; i++) {
int count = 0;
for (int j = 0; j < tab.length; j++) {
if(i + smallSquareSize <= tab.length && j + smallSquareSize <= tab.length) {
for (int x = 0; x < smallSquareSize; x++) {
for (int z = 0; z < smallSquareSize; z++) {
count = count + tab[i + x][j + z];
}
}
}
else break;
if (endCount < count) {
endCount = count;
}
count = 0;
}
}
```

I am looping through every single element in a big square and from here I ‘make’ a smaller one. Then I am looping through every element in the small one and count the “1”.

For the example above, the answer is 23 and smaller square starts at row 3 column 1 (starting at 0,0).

It works well for smaller arrays, but I need it to work on like 5000 elements side squares. I know that this is probably the dumbest solution possible, but I have no idea how to get rid of any of those for loops to make it run faster.

It may be better to pre-calculate some parts of the input array/matrix (e.g. the sums in the vertical “strips” with `height = smallSquareSize` and `width = 1`) and store these sub-sums in another array which would require slightly less space: `int[][] sub = new int[rows - smallSquareSize + 1][cols];`

Then the sums for the vertical strips are counted for `cols * (rows - smallSquareSize + 1)` which is basically O(N2), and the sums of the subsquares are calculated similarly for O(N2) `(rows - smallSquareSize + 1) * cols`:

```public static int maxSum(int smallSquareSize, int[][] arr) {
int rows = arr.length;
int cols = arr[0].length;

int[][] sub = new int[rows - smallSquareSize + 1][cols];
for (int c = 0; c < cols; c++) {
int sum = 0;
for (int r = 0; r < smallSquareSize; r++) {
sum += arr[r][c];
}
sub[0][c] = sum;
for (int r = 1; r < sub.length; r++) {
sum += arr[r + smallSquareSize - 1][c] - arr[r - 1][c];
sub[r][c] = sum;
}
}
// debug print
System.out.println("Sub-sums:");
for (int r = 0; r < sub.length; r++) {
System.out.println(Arrays.toString(sub[r]));
}

int max = Integer.MIN_VALUE;

for (int r = 0; r < sub.length; r++) {
// calculate subsquare sum
int squareSum = 0;
for (int c = 0; c < smallSquareSize; c++) {
squareSum += sub[r][c];
}
// debug print
System.out.print("s[" + r + "][" + 0 + "]=" + squareSum);
if (max < squareSum) {
max = squareSum;
}

// subtract previous and add next column to quickly get next subsquare
for (int c = 1; c < cols - smallSquareSize + 1; c++) {
squareSum += sub[r][c + smallSquareSize - 1] - sub[r][c - 1];

// debug print
System.out.print("ts[" + r + "][" + c + "]=" + squareSum);
if (max < squareSum) {
max = squareSum;
}
}
System.out.println();
}
return max;
}
```

For the given input the results are as follows:

```int[][] matrix = {
{0,1,1,1,1,0,1,0,1,0}, {1,0,0,0,0,1,0,1,1,0},
{1,0,0,1,0,0,1,0,0,0}, {1,1,1,0,0,1,1,0,0,1},
{1,1,1,1,1,1,0,0,1,0}, {0,0,1,1,1,1,0,0,0,0},
{0,0,0,1,1,0,1,0,0,0}, {0,0,0,1,1,0,1,0,1,0},
{0,1,1,0,1,0,1,1,0,1}, {0,0,0,1,0,0,0,0,0,1},
};
System.out.println("Max Sum: " + maxSum(6, matrix));
```

Output with debug messages:

```Sub-sums:
[4, 3, 4, 4, 3, 4, 3, 1, 3, 1]
[4, 2, 3, 4, 3, 4, 3, 1, 2, 1]
[3, 2, 3, 5, 4, 3, 4, 0, 2, 1]
[2, 3, 4, 4, 5, 3, 4, 1, 2, 2]
[1, 2, 3, 5, 5, 2, 3, 1, 2, 2]
s[0][0]=22  s[0][1]=21  s[0][2]=19  s[0][3]=18  s[0][4]=15
s[1][0]=20  s[1][1]=19  s[1][2]=18  s[1][3]=17  s[1][4]=14
s[2][0]=20  s[2][1]=21  s[2][2]=19  s[2][3]=18  s[2][4]=14
s[3][0]=21  s[3][1]=23  s[3][2]=21  s[3][3]=19  s[3][4]=17
s[4][0]=18  s[4][1]=20  s[4][2]=19  s[4][3]=18  s[4][4]=15
Max Sum: 23
```