1895. Largest Magic Square

Problem Description

In this problem, you are given a grid, which is an m x n matrix of integers. Your task is to find the largest "magic square" that can exist within this grid. A "magic square" is a subgrid which is of size k x k, where every row, every column, and both the diagonals sum up to the same value. This same value does not need to be unique across different magic squares within the grid. It is also mentioned that 1 x 1 grids are considered magic squares, being the smallest possible size.

The goal is to return the size (that is, the length of a side) of the largest magic square that you can find in the provided grid. The elements in the grid are not required to be unique.

Intuition

When finding the solution to this problem, the intuitive approach is to check all possible subgrids in a brute force manner, by checking every k x k subgrid (start from the largest possible k and decrement) for being a magic square.

The naive approach would be to calculate the sum of rows, columns, and diagonals for each possible subgrid from scratch which would lead to a high time complexity. Instead, we precompute cumulative row sums and column sums to enable constant-time queries of the sum of any row segment or column segment, which makes the solution much faster and more efficient.

The idea is to construct two auxiliary matrices: rowsum and colsum. For any cell (i, j), rowsum[i][j] contains the sum of the first j elements of row i in the grid, and colsum[i][j] contains the sum of the first i elements of column j in the grid. Once we have these cumulative sums, we can quickly calculate the sum of any row or column segment within a magic square candidate by subtracting the appropriate values from rowsum and colsum.

The check function inside the solution uses this approach to check if a potential k x k subgrid is a magic square: it compares the sum of rows, columns, and both diagonals to a target value (the sum calculated for the first row or column in the subgrid being checked). If all of them are equal to this value, then we've found a magic square.

Starting from the largest possible size k (which would be the minimum of m and n), we check each possible subgrid of size k to see if it is a magic square. If a magic square is found, it is currently the largest one, and we return the size k. If not, we decrement k and continue checking until we find a magic square or reach the smallest size, which is 1.

The use of cumulative sum arrays and the optimization of starting from the largest possible square size and working downwards allows this solution to be efficient enough to handle the problem within acceptable time limits.

Learn more about Prefix Sum patterns.

Solution Approach

The solution is implemented using a few notable algorithms, data structures, and patterns which can be broken down into the following steps:

1. Precomputation of Sums: Before we start searching for the magic square, we precompute the cumulative sums of the rows and columns. This is done using two 2D arrays, rowsum and colsum. These arrays are of size (m+1) x (n+1) to account for ease of index management and to avoid out-of-bound errors when querying the sums. This helps in reducing the complexity of sum calculations within the subgrids from O(k) to O(1), where k is the size of the potential magic square.

2. Checking for Magic Squares: A nested function check(x1, y1, x2, y2) is used to verify if a subgrid with the upper left corner (x1, y1) and the lower right corner (x2, y2) is a magic square. This function:

   • Calculates and stores the sum of the first row of the subgrid.
   • Iterates over the remaining rows, checking if their sum matches the first row's sum using the precomputed sums in rowsum.
   • Does the same process for the columns using the colsum.
   • Next, it calculates the sums for both the diagonals separately and checks if they too match the sum of the first row.
   • If all these sums are equal, the subgrid is indeed a magic square.

3. Iterating Over Subgrid Sizes: The main part of the solution starts with the largest possible subgrid size k, which is the minimum dimension of the grid (since a magic square has to be square-shaped). A double loop is used to iterate over all possible subgrid origins.

   • For each possible origin (i, j), the function calls check(i, j, i+k-1, j+k-1), which looks at the subgrid formed from over (i, j) to (i+k-1, j+k-1).
   • If check returns True, then a magic square has been found, and the size k is returned.
   • If no magic square is found, we decrement k and continue searching until k reaches 1 (since every 1x1 grid is trivially a magic square).

4. Returning the Size of the Largest Magic Square: If the code did not find any magic square larger than 1x1, we return 1. Otherwise, the value of k when check function first returns True is returned, indicating the largest magic square's side length.

The key data structures used in this approach are two-dimensional arrays (lists in Python) to store the cumulative sum of rows and columns which enable us to quickly calculate the sums of row and column segments. The algorithm follows a brute-force pattern with optimization. It iteratively checks the subgrids for being a magic square, starting from the largest possible k and decreasing until it finds the largest magic square or all possibilities have been exhausted.

Example Walkthrough

Let's illustrate the solution approach using a small 4x4 grid as an example, where the grid matrix is as follows:

1grid = [
2    [16, 23, 17, 10],
3    [22, 3,  8,  1],
4    [24, 4,  14, 5],
5    [15, 7,  2,  13]
6]

We want to find the largest magic square in this grid.

1. Precomputation of Sums

First, we precompute the cumulative sums for rows and columns. For example, the rowsum for the second row would be [22, 25, 33, 34] meaning that the sum of the first element is 22, of the first two is 25, and so on. The colsum for the second column would be [23, 26, 30, 37] for the respective rows.

After precomputation, our rowsum and colsum might look something like this:

rowsum:

1[
2    [0, 16, 39, 56, 66],
3    [0, 22, 25, 33, 34],
4    [0, 24, 28, 42, 47],
5    [0, 15, 22, 24, 37]
6]

colsum:

1[
2    [0, 0, 0, 0, 0],
3    [16, 16, 23, 17, 10],
4    [38, 22, 26, 25, 11],
5    [62, 46, 30, 39, 16],
6    [77, 61, 37, 52, 29]
7]

2. Checking for Magic Squares

Now, suppose we want to check if the 2x2 subgrid starting at the top left corner (0, 0) is a magic square. We use the check function to calculate the sums of rows, columns, and diagonals. Since for a 2x2 subgrid the sums are only needed for 2 rows and 2 columns, the calculations are quite straightforward:

• Sum of the first row [16, 23] is rowsum[1][2] - rowsum[1][0] = 39 - 16 = 23.
• Sum of the second row [22, 3] is rowsum[2][2] - rowsum[2][0] = 25 - 22 = 3.
• We notice the sums do not match, so without further checks, we can conclude this is not a magic square.

3. Iterating Over Subgrid Sizes

Let's now use the largest possible square size k=4 (since our grid is 4x4) and iterate over all possible subgrid origins. We quickly realize that it's not possible to form a magic square of size 4x4 because the grid itself is that size, and the sums of the rows and columns are evidently not equal.

Therefore, we decrease k to 3 and test every 3x3 subgrid by checking starting points (0,0), (0,1), (1,0), and (1,1). If none is a magic square, we continue with k=2 and check every 2x2 subgrid in a similar manner.

4. Returning the Size of the Largest Magic Square

In our example, we would eventually find that there is no magic square of size k=3, and upon checking all 2x2 subgrids, we ascertain that there aren't any of size k=2 either. Thus, we conclude with k=1 being the largest magic square size, where each element individually can be considered a magic square.

This example demonstrates how the algorithm checks many possibilities efficiently by using the precomputed sums, starting from the largest square size, and progressively going down to smaller square sizes until the largest magic square in the grid is found or reaching 1x1 grids.

Solution Implementation

Time and Space Complexity

Time Complexity:

The time complexity of the code is determined by several nested loops and operations within the check function that is called for different sizes of potential magic squares.

1. The first two loops (over i and j) are used to compute the cumulative row sums and column sums. These loops run over the dimensions of the grid, with m rows and n columns. Therefore, this part has a time complexity of O(m * n).

2. The main part of the algorithm tries to find the largest magic square by checking squares of decreasing size k (side length of the square). It iterates over all possible top-left corners (i, j) of squares with side lengths ranging from min(m, n) down to 2. This results in a three-level nested loop structure.

For each fixed size k, there are (m - k + 1) * (n - k + 1) possible positions to place the square. For each position, the check function is called, which itself contains loops that run up to k times.

The time complexity for verifying each square is O(k) since it involves checking k rows, k columns, and two diagonals (which also take O(k) time).

Combining the loops for trying different square sizes and positions, the time complexity would be:

O(sum_{k=2}^{min(m,n)}(m - k + 1) * (n - k + 1) * k) O(sum_{k=2}^{min(m,n)}(mnk - nk^2 - mk^2 + k^3))

which in the worst case simplifies to the cubic complexity O(m * n * min(m, n)) when m and n are fairly close in size.

Space Complexity:

1. The space complexity is primarily determined by the extra space for the rowsum and colsum arrays, each of which is sized (m + 1) * (n + 1) to accommodate the cumulative sums along the rows and columns. Therefore, the space complexity for these arrays is O(m * n).

2. The check function uses constant extra space, in terms of a few variables to store sums and loop indices.

Overall, the space complexity is O(m * n) for storing cumulative row and column sums.

Learn more about how to find time and space complexity quickly using problem constraints.