Largest Magic Square - Video Solutions

Problem Overview: Given a grid of integers, find the size of the largest k x k subgrid where every row sum, column sum, and both diagonal sums are equal. Such a subgrid is called a magic square. The task is to scan the matrix and return the maximum possible k.

Approach 1: Brute Force with Prefix Sums (Time: O(m * n * k^2), Space: O(m * n))

Start by computing prefix sums for rows and columns so you can query the sum of any row segment or column segment in constant time. For every possible top-left corner in the matrix, try every possible square size k. For each candidate square, check all k row sums and k column sums using the prefix arrays, and compute the two diagonals directly. If every sum matches the first row's sum, the square is magic. This approach is straightforward and easier to reason about, but verifying all rows and columns for every candidate square introduces an extra k factor.

Prefix sums are the key helper here. A row prefix array lets you compute sum(row, c1..c2) instantly, while a column prefix array provides sum(col, r1..r2). That avoids recomputing sums repeatedly and significantly reduces the naive O(k^3) checks. This technique is common in problems involving repeated range queries on arrays and grids.

Approach 2: Optimized Prefix Sum Verification (Time: O(m * n * min(m,n)), Space: O(m * n))

This approach still relies on prefix sums but reduces unnecessary checks. Precompute row and column prefix sums once. Then iterate over possible square sizes from largest to smallest. For each size k, scan all valid top-left positions. Compute the target sum from the first row of the square. Next verify columns using prefix sums and compute the two diagonals directly. Because you attempt larger squares first, you can return immediately once a valid magic square is found.

The optimization works because prefix sums reduce every row and column verification to O(1). The algorithm effectively checks each candidate square in linear time relative to its size rather than quadratic. Combined with early termination when a valid square appears, this performs well even for larger grids.

Recommended for interviews: The optimized prefix sum approach is what most interviewers expect. The brute force version shows that you understand how to enumerate candidate squares and validate sums. Adding prefix sums and checking larger squares first demonstrates practical optimization skills and familiarity with common grid techniques.