Searching for patterns in a grid is a classic challenge in algorithmic thinking. In this problem, we are tasked with finding the largest possible sub-grid where every row, column, and both main diagonals add up to the exact same value.
You're given:
- An integer grid.
- A definition of a Magic Square: a sub-grid where the sum of every row, every column, and both diagonals are equal.
Your goal:
- Find and return the maximum side length of any magic square hidden within the grid.
Example 1 :
Input: grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
Output: 3
Explanation: The largest magic square has a size of 3.
Every row sum, column sum, and diagonal sum of this magic square is equal to 12.
- Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Diagonal sums: 5+4+3 = 6+4+2 = 12
Example 2 :
Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
Output: 2
Constrains :
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- 1 <= grid[i][j] <= 106
Intuition
The brute-force approach would be to check every possible square of every size and manually sum up its rows, columns, and diagonals. However, that involves a lot of repeated work. To make this efficient, we use a technique called Prefix Sums.
Think of a prefix sum like a "running total." If you know the total sum of a row from the start up to index 10, and the total sum up to index 5, you can find the sum of the elements between 5 and 10 instantly by subtracting the two totals.
In this solution, we pre-calculate four types of running totals for every cell :
- Horizontal: Sum of elements in that row.
- Vertical: Sum of elements in that column.
- Main Diagonal: Sum of elements moving from top-left to bottom-right.
- Anti-Diagonal: Sum of elements moving from top-right to bottom-left.
Once we have these tables, checking if a square is "magic" becomes a matter of simple subtraction rather than looping through every single cell. We start searching from the largest possible side length (the minimum of and ) and work our way down. The first one that satisfies the magic square condition is our answer.
Code Blocks
C++
class Solution {
public:
bool isMagic(vector<vector<array<int,4>>> const & prefixSum, int r, int c, int sz) {
// Calculate the main diagonal sum
int targetSum = prefixSum[r+sz][c+sz][2] - prefixSum[r][c][2];
// Check the anti-diagonal sum
if (targetSum != prefixSum[r+sz][c+1][3] - prefixSum[r][c+sz+1][3]) {
return false;
}
// Check all row sums within the square
for (int j = r; j < r + sz; j++) {
if (targetSum != prefixSum[j+1][c+sz][0] - prefixSum[j+1][c][0]) {
return false;
}
}
// Check all column sums within the square
for (int j = c; j < c + sz; j++) {
if (targetSum != prefixSum[r+sz][j+1][1] - prefixSum[r][j+1][1]) {
return false;
}
}
return true;
}
int largestMagicSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
// prefixSum stores: [row, col, diag, anti-diag] sums
vector<vector<array<int,4>>> prefixSum(m + 1, vector<array<int,4>>(n + 2));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int val = grid[i-1][j-1];
prefixSum[i][j][0] = prefixSum[i][j-1][0] + val; // Row
prefixSum[i][j][1] = prefixSum[i-1][j][1] + val; // Col
prefixSum[i][j][2] = prefixSum[i-1][j-1][2] + val; // Diag
prefixSum[i][j][3] = prefixSum[i-1][j+1][3] + val; // Anti-Diag
}
}
for (int k = min(m, n); k >= 2; k--) {
for (int i = 0; i <= m - k; i++) {
for (int j = 0; j <= n - k; j++) {
if (isMagic(prefixSum, i, j, k)) return k;
}
}
}
return 1;
}
};
Python
class Solution:
def largestMagicSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# prefixSum[i][j] stores [row, col, diag, anti_diag]
# We add padding to handle boundary conditions easily
pref = [[[0] * 4 for _ in range(n + 2)] for _ in range(m + 1)]
for r in range(1, m + 1):
for c in range(1, n + 1):
val = grid[r-1][c-1]
pref[r][c][0] = pref[r][c-1][0] + val
pref[r][c][1] = pref[r-1][c][1] + val
pref[r][c][2] = pref[r-1][c-1][2] + val
pref[r][c][3] = pref[r-1][c+1][3] + val
def is_magic(r, c, k):
# Target sum from the main diagonal
target = pref[r+k][c+k][2] - pref[r][c][2]
# Check anti-diagonal
if target != pref[r+k][c+1][3] - pref[r][c+k+1][3]:
return False
# Check all rows
for i in range(r, r + k):
if pref[i+1][c+k][0] - pref[i+1][c][0] != target:
return False
# Check all columns
for j in range(c, c + k):
if pref[r+k][j+1][1] - pref[r][j+1][1] != target:
return False
return True
# Check from largest possible side length downwards
for k in range(min(m, n), 1, -1):
for i in range(m - k + 1):
for j in range(n - k + 1):
if is_magic(i, j, k):
return k
return 1
JavaScript
/**
* @param {number[][]} grid
* @return {number}
*/
var largestMagicSquare = function(grid) {
const m = grid.length;
const n = grid[0].length;
// Create prefix sum 3D array: [m+1][n+2][4]
const pref = Array.from({ length: m + 1 }, () =>
Array.from({ length: n + 2 }, () => new Int32Array(4))
);
for (let r = 1; r <= m; r++) {
for (let c = 1; c <= n; c++) {
const val = grid[r-1][c-1];
pref[r][c][0] = pref[r][c-1][0] + val; // Row
pref[r][c][1] = pref[r-1][c][1] + val; // Col
pref[r][c][2] = pref[r-1][c-1][2] + val; // Diag
pref[r][c][3] = pref[r-1][c+1][3] + val; // Anti-Diag
}
}
const isMagic = (r, c, k) => {
const target = pref[r+k][c+k][2] - pref[r][c][2];
if (target !== pref[r+k][c+1][3] - pref[r][c+k+1][3]) return false;
for (let i = r; i < r + k; i++) {
if (pref[i+1][c+k][0] - pref[i+1][c][0] !== target) return false;
}
for (let j = c; j < c + k; j++) {
if (pref[r+k][j+1][1] - pref[r][j+1][1] !== target) return false;
}
return true;
};
for (let k = Math.min(m, n); k >= 2; k--) {
for (let i = 0; i <= m - k; i++) {
for (let j = 0; j <= n - k; j++) {
if (isMagic(i, j, k)) return k;
}
}
}
return 1;
};
Key Takeaways
- Prefix Sums in 2D: This technique is a powerhouse for range-sum queries in grids, reducing the time complexity of checking a sub-grid from to for each row or column.
-
Space-Time Tradeoff: By using extra memory to store our
prefixSumtables, we significantly speed up the validation process for each potential square. - Greedy Optimization: Searching from the largest possible down to 2 allows us to return the answer immediately upon finding a match, saving unnecessary computations.
Final Thoughts
As a mentor, I often see students struggle with grid problems because they try to "count" everything manually. Learning to use prefix sums is like leveling up your vision in game development or data processing: you stop seeing individual pixels and start seeing regions. This problem is excellent practice for interviews at companies like Google or Amazon, where multidimensional array manipulation and optimization are frequently tested. In the real world, these concepts are the foundation for image processing filters and spatial data analysis.
Top comments (0)