Problem Statement
Medium
A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given a row x col grid of integers, how many 3 x 3 contiguous magic square subgrids are there?
Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.
Example 1:
Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation:
The following subgrid is a 3 x 3 magic square:
while this one is not:
In total, there is only one magic square inside the given grid.
Example 2:
Input: grid = [[8]]
Output: 0
Constraints:
row == grid.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15
class Solution {
public int numMagicSquaresInside(int[][] grid) {
int m = grid.length, n = grid[0].length, ans = 0;
for (int i = 0; i < m - 2; i++)
for (int j = 0; j < n - 2; j++)
if (isMagicSq(grid, i, j))
ans++;
return ans;
}
private boolean isMagicSq(int[][] grid, int rowStart, int colStart) {
int[] rowSum = new int[3];
int[] colSum = new int[3];
int[] diagSum = new int[2];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int cell = grid[rowStart + i][colStart + j];
if (cell == 0 || cell > 9)
return false;
rowSum[i] += cell;
colSum[i] += grid[rowStart + j][colStart + i];
}
diagSum[0] += grid[rowStart + i][colStart + i];
diagSum[1] += grid[rowStart + i][colStart + 2 - i];
}
// System.out.println(Arrays.toString(rowSum));
// System.out.println(Arrays.toString(colSum));
// System.out.println(Arrays.toString(diagSum));
int match = diagSum[0];
for (int i = 0; i < 3; i++)
if (rowSum[i] != match || colSum[i] != match)
return false;
return match == diagSum[1];
}
}