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:
-
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
andcolsum
. 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 fromO(k)
toO(1)
, wherek
is the size of the potential magic square. -
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.
-
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 callscheck(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
returnsTrue
, then a magic square has been found, and the sizek
is returned. - If no magic square is found, we decrement
k
and continue searching untilk
reaches 1 (since every1x1
grid is trivially a magic square).
- For each possible origin
-
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 ofk
whencheck
function first returnsTrue
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small 4x4
grid as an example, where the grid matrix is as follows:
grid = [ [16, 23, 17, 10], [22, 3, 8, 1], [24, 4, 14, 5], [15, 7, 2, 13] ]
We want to find the largest magic square in this grid.
- 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
:
[ [0, 16, 39, 56, 66], [0, 22, 25, 33, 34], [0, 24, 28, 42, 47], [0, 15, 22, 24, 37] ]
colsum
:
[ [0, 0, 0, 0, 0], [16, 16, 23, 17, 10], [38, 22, 26, 25, 11], [62, 46, 30, 39, 16], [77, 61, 37, 52, 29] ]
- 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]
isrowsum[1][2] - rowsum[1][0] = 39 - 16 = 23
. - Sum of the second row
[22, 3]
isrowsum[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.
- 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.
- 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
1from typing import List
2
3class Solution:
4 def largestMagicSquare(self, grid: List[List[int]]) -> int:
5 # Get the dimensions of the grid
6 rows, cols = len(grid), len(grid[0])
7
8 # Initialize prefix sum matrices for rows and columns
9 row_prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
10 col_prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
11
12 # Calculate prefix sums for rows and columns
13 for i in range(rows):
14 for j in range(cols):
15 row_prefix[i + 1][j + 1] = row_prefix[i + 1][j] + grid[i][j]
16 col_prefix[i + 1][j + 1] = col_prefix[i][j + 1] + grid[i][j]
17
18 # Define a function to check if a square is magic
19 def is_magic_square(x1, y1, x2, y2):
20 target_sum = row_prefix[x1 + 1][y2 + 1] - row_prefix[x1 + 1][y1]
21
22 # Check rows
23 for i in range(x1 + 1, x2 + 1):
24 if row_prefix[i + 1][y2 + 1] - row_prefix[i + 1][y1] != target_sum:
25 return False
26
27 # Check columns
28 for j in range(y1, y2 + 1):
29 if col_prefix[x2 + 1][j + 1] - col_prefix[x1][j + 1] != target_sum:
30 return False
31
32 # Check diagonal from top-left to bottom-right
33 diag_sum = sum(grid[x1 + d][y1 + d] for d in range(x2 - x1 + 1))
34 if diag_sum != target_sum:
35 return False
36
37 # Check diagonal from top-right to bottom-left
38 diag_sum = sum(grid[x1 + d][y2 - d] for d in range(x2 - x1 + 1))
39 if diag_sum != target_sum:
40 return False
41
42 return True
43
44 # Loop from largest possible square size down to 2
45 # as the smallest magic square is of size 1 by definition
46 for size in range(min(rows, cols), 1, -1):
47 for i in range(rows - size + 1):
48 for j in range(cols - size + 1):
49 if is_magic_square(i, j, i + size - 1, j + size - 1):
50 return size
51
52 # If no magic square larger than 1 is found, return 1
53 return 1
54
1class Solution {
2 private int[][] rowSum;
3 private int[][] colSum;
4
5 // This method finds the largest magic square within a given grid.
6 public int largestMagicSquare(int[][] grid) {
7 int m = grid.length, n = grid[0].length;
8 // Initialize prefix sums for rows and columns.
9 rowSum = new int[m + 1][n + 1];
10 colSum = new int[m + 1][n + 1];
11
12 // Populate the prefix sums.
13 for (int i = 1; i <= m; ++i) {
14 for (int j = 1; j <= n; ++j) {
15 rowSum[i][j] = rowSum[i][j - 1] + grid[i - 1][j - 1];
16 colSum[i][j] = colSum[i - 1][j] + grid[i - 1][j - 1];
17 }
18 }
19
20 // Iterate from the largest possible square to the smallest.
21 for (int k = Math.min(m, n); k > 1; --k) {
22 for (int i = 0; i + k - 1 < m; ++i) {
23 for (int j = 0; j + k - 1 < n; ++j) {
24 // Calculate the rightmost and bottommost indices.
25 int i2 = i + k - 1, j2 = j + k - 1;
26 // Check if the current subset of the grid is a magic square.
27 if (isMagicSquare(grid, i, j, i2, j2)) {
28 return k; // Return the size of the largest magic square.
29 }
30 }
31 }
32 }
33 // If there is no magic square larger than size 1, return 1.
34 return 1;
35 }
36
37 // This method checks if a subset of the grid defined by the top-left
38 // and bottom-right coordinates is a magic square.
39 private boolean isMagicSquare(int[][] grid, int x1, int y1, int x2, int y2) {
40 // Calculate the value to compare against (first row's sum).
41 int targetValue = rowSum[x1 + 1][y2 + 1] - rowSum[x1 + 1][y1];
42
43 // Check if all row sums are equal to the target value.
44 for (int i = x1 + 1; i <= x2; ++i) {
45 if (rowSum[i + 1][y2 + 1] - rowSum[i + 1][y1] != targetValue) {
46 return false;
47 }
48 }
49
50 // Check if all column sums are equal to the target value.
51 for (int j = y1; j <= y2; ++j) {
52 if (colSum[x2 + 1][j + 1] - colSum[x1][j + 1] != targetValue) {
53 return false;
54 }
55 }
56
57 // Check the sum of the diagonal from top-left to bottom-right.
58 int diagonalSum = 0;
59 for (int i = x1, j = y1; i <= x2; ++i, ++j) {
60 diagonalSum += grid[i][j];
61 }
62 if (diagonalSum != targetValue) {
63 return false;
64 }
65
66 // Check the sum of the diagonal from top-right to bottom-left.
67 diagonalSum = 0;
68 for (int i = x1, j = y2; i <= x2; ++i, --j) {
69 diagonalSum += grid[i][j];
70 }
71 // Check if the second diagonal sum is also equal to the target value.
72 if (diagonalSum != targetValue) {
73 return false;
74 }
75
76 // If all checks passed, it's a magic square.
77 return true;
78 }
79}
80
1class Solution {
2public:
3 // Function to find the largest magic square in the given grid
4 int largestMagicSquare(vector<vector<int>>& grid) {
5 int m = grid.size(), n = grid[0].size();
6 // Create prefix sum arrays for rows and columns
7 vector<vector<int>> rowSum(m + 1, vector<int>(n + 1));
8 vector<vector<int>> colSum(m + 1, vector<int>(n + 1));
9
10 // Fill prefix sum arrays
11 for (int i = 1; i <= m; ++i) {
12 for (int j = 1; j <= n; ++j) {
13 rowSum[i][j] = rowSum[i][j - 1] + grid[i - 1][j - 1];
14 colSum[i][j] = colSum[i - 1][j] + grid[i - 1][j - 1];
15 }
16 }
17
18 // Search for the largest magic square beginning from the largest possible size
19 for (int k = min(m, n); k > 1; --k) {
20 for (int i = 0; i + k - 1 < m; ++i) {
21 for (int j = 0; j + k - 1 < n; ++j) {
22 int i2 = i + k - 1, j2 = j + k - 1;
23 // Check if the current square is a magic square
24 if (checkMagicSquare(grid, rowSum, colSum, i, j, i2, j2))
25 return k; // Return size if it's a magic square
26 }
27 }
28 }
29
30 // If no larger magic square is found, return 1 as the default size
31 return 1;
32 }
33
34 // Function to check if a square is magic
35 bool checkMagicSquare(vector<vector<int>>& grid, vector<vector<int>>& rowSum, vector<vector<int>>& colSum,
36 int topLeftX, int topLeftY, int bottomRightX, int bottomRightY) {
37 // The value that rows, columns, and diagonals should sum to
38 int targetSum = rowSum[topLeftX + 1][bottomRightY + 1] - rowSum[topLeftX + 1][topLeftY];
39
40 // Check sums of all rows
41 for (int i = topLeftX + 1; i <= bottomRightX; ++i)
42 if (rowSum[i + 1][bottomRightY + 1] - rowSum[i + 1][topLeftY] != targetSum)
43 return false;
44
45 // Check sums of all columns
46 for (int j = topLeftY; j <= bottomRightY; ++j)
47 if (colSum[bottomRightX + 1][j + 1] - colSum[topLeftX][j + 1] != targetSum)
48 return false;
49
50 // Check diagonal (top-left to bottom-right)
51 int sumDiagonal = 0;
52 for (int i = topLeftX, j = topLeftY; i <= bottomRightX; ++i, ++j)
53 sumDiagonal += grid[i][j];
54 if (sumDiagonal != targetSum)
55 return false;
56
57 // Check anti-diagonal (top-right to bottom-left)
58 sumDiagonal = 0;
59 for (int i = topLeftX, j = bottomRightY; i <= bottomRightX; ++i, --j)
60 sumDiagonal += grid[i][j];
61 if (sumDiagonal != targetSum)
62 return false;
63
64 // If all checks pass, it's a magic square
65 return true;
66 }
67};
68
1function largestMagicSquare(grid: number[][]): number {
2 const rows = grid.length;
3 const cols = grid[0].length;
4
5 // Create prefix sums for rows and columns
6 let rowPrefixSum = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
7 let colPrefixSum = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
8
9 // Compute row prefix sums
10 for (let i = 0; i < rows; i++) {
11 rowPrefixSum[i + 1][1] = grid[i][0];
12 for (let j = 1; j < cols; j++) {
13 rowPrefixSum[i + 1][j + 1] = rowPrefixSum[i + 1][j] + grid[i][j];
14 }
15 }
16
17 // Compute column prefix sums
18 for (let j = 0; j < cols; j++) {
19 colPrefixSum[1][j + 1] = grid[0][j];
20 for (let i = 1; i < rows; i++) {
21 colPrefixSum[i + 1][j + 1] = colPrefixSum[i][j + 1] + grid[i][j];
22 }
23 }
24
25 // Search for the largest magic square
26 for (let k = Math.min(rows, cols); k > 1; k--) {
27 for (let i = 0; i + k - 1 < rows; i++) {
28 for (let j = 0; j + k - 1 < cols; j++) {
29 let x2 = i + k - 1;
30 let y2 = j + k - 1;
31 if (isMagicSquare(grid, rowPrefixSum, colPrefixSum, i, j, x2, y2)) {
32 return k;
33 }
34 }
35 }
36 }
37
38 return 1;
39}
40
41function isMagicSquare(
42 grid: number[][],
43 rowPrefixSum: number[][],
44 colPrefixSum: number[][],
45 x1: number,
46 y1: number,
47 x2: number,
48 y2: number
49): boolean {
50 // Check if the sums are equal for all rows, columns and both diagonals
51
52 // Initialize the comparison sum based on the first row
53 const targetSum = rowPrefixSum[x1 + 1][y2 + 1] - rowPrefixSum[x1 + 1][y1];
54
55 // Check rows
56 for (let i = x1 + 1; i <= x2; i++) {
57 if (targetSum !== rowPrefixSum[i + 1][y2 + 1] - rowPrefixSum[i + 1][y1]) {
58 return false;
59 }
60 }
61
62 // Check columns
63 for (let j = y1; j <= y2; j++) {
64 if (targetSum !== colPrefixSum[x2 + 1][j + 1] - colPrefixSum[x1][j + 1]) {
65 return false;
66 }
67 }
68
69 // Check main diagonal
70 let mainDiagonalSum = targetSum;
71 for (let i = x1, j = y1; i <= x2; i++, j++) {
72 mainDiagonalSum -= grid[i][j];
73 }
74 if (mainDiagonalSum !== 0) return false;
75
76 // Check secondary diagonal
77 let secondaryDiagonalSum = targetSum;
78 for (let i = x1, j = y2; i <= x2; i++, j--) {
79 secondaryDiagonalSum -= grid[i][j];
80 }
81 if (secondaryDiagonalSum !== 0) return false;
82
83 return true;
84}
85
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.
-
The first two loops (over
i
andj
) are used to compute the cumulative row sums and column sums. These loops run over the dimensions of the grid, withm
rows andn
columns. Therefore, this part has a time complexity ofO(m * n)
. -
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 frommin(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:
-
The space complexity is primarily determined by the extra space for the
rowsum
andcolsum
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 isO(m * n)
. -
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.
Which type of traversal does breadth first search do?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!