Problem
A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.
Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.
Approach
A magic square should have its sum of every row, column and diagonals be the same. However, there will be many repetition in calculating the sums. For example, with a 3 x 3 square, to check if this square is a magic square, we first calculate all the sum of each rows, columns and diagonals. If this 3 by 3 square is not a magic square we move on checking if the 2 x 2 (starting from the top right, (0, 0)) is a magic square. Here, we sort of calculated the sum already when checking the 3 x 3 square and we could make our solution faster by eliminating the repeated calculations.
Solution
In this solution, we are using prefix sum. We first calculate the each row, column and the diagonal’s prefix sum, therefore, we could quicky get the sum when dealing with all different sizes of square in $O(1)$.
The rest should be simple, starting from (0, 0), we iterate through all the numbers in the input matrix and try build a square from it. We should start from the largest square with the starting location in the matrix and skip all the squares that is smaller than the current largest magic square size to further decrease the redundant calculations.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
int largestMagicSquare(std::vector<std::vector<int>>& grid) {
int m = grid.size(), n = grid.front().size();
int largestSize = 1;
std::vector<std::vector<int>> row, col, diag, rdiag;
row = col = diag = rdiag = grid;
// build prefix sum
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j != 0) row[i][j] += row[i][j-1];
if (i != 0) col[i][j] += col[i-1][j];
if (i != 0 && j != 0) diag[i][j] += diag[i-1][j-1];
if (i != 0 && j != 0) rdiag[i][n-j-1] += rdiag[i-1][n-j];
}
}
// check if magic square
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// starting from the largest square possible and skip all the
// square that are smaller than the current largest magic squrare
for (int size = std::min(m-i, n-j); size > largestSize; size--) {
bool magic = true;
// diagonal
int sum = diag[i+size-1][j+size-1] - ((i-1 < 0 || j-1 < 0)? 0: diag[i-1][j-1]);
magic = sum == rdiag[i+size-1][j] - ((i-1 < 0 || j+size >= n)? 0: rdiag[i-1][j+size]);
// check each row, column
for (int k = 0; k < size; k++) {
magic &= sum == row[i+k][j+size-1] - ((j-1 < 0)? 0: row[i+k][j-1]);
magic &= sum == col[i+size-1][j+k] - ((i-1 < 0)? 0: col[i-1][j+k]);
}
if (magic) largestSize = std::max(largestSize, size);
}
}
}
return largestSize;
}
};