\u2714\uFE0F ***Solution - I (Brute-Force)***\n\nStart with the max size square and check each row, column and both diagonals sum. The constraints are small enough that the brute force solution would pass. The only difficult thing in this question is proper implementation and avoiding overflowing the bounds.\n\n```\n// brute-force\nint largestMagicSquare(vector>& grid) {\n\tint m = size(grid), n = size(grid[0]);\n\tfor(int sz = min(m, n); sz > 1; sz--) // start from max-sized square\n\t\tfor(int row = 0; row <= m - sz; row++) // iterate over all starting row index for sqaure of side=sz\n\t\t\tfor(int col = 0; col <= n - sz; col++) { // iterate over all starting col index for sqaure of side=sz\n\t\t\t\tint row_sum = 0, col_sum = 0, diag_sum = 0, anti_diag_sum = 0; \n bool flg = true;\n\n\t\t\t\tfor(int i = 0; i < sz; i++) row_sum += grid[row][col + i]; // 1st row sum of current square\n\t\t\t\tfor(int i = 0; i < sz; i++) col_sum += grid[row + i][col]; // 1st col sum of current square\n\t\t\t\tfor(int i = 0; i < sz; i++) diag_sum += grid[row + i][col + i];// normal diagonal sum of current square\n\t\t\t\tfor(int i = 0; i < sz; i++) anti_diag_sum += grid[row + i][col + (sz-1) - i]; // anti-diagonal sum of current square\n\t\t\t\t// if either of row/col/diag/anti-diag sums don\'t match, this square isn\'t magic square\n\t\t\t\tif(diag_sum != anti_diag_sum || diag_sum != row_sum || diag_sum != col_sum) continue;\n\t\t\t\t\n\t\t\t\t// check if all rows have same sum\n\t\t\t\tfor(int i{1}, cur_row_sum{0}; i < sz && flg; i++, cur_row_sum=0) {\n\t\t\t\t\tfor(int j = 0; j < sz; j++) \n\t\t\t\t\t\tcur_row_sum += grid[row + i][col + j];\n\t\t\t\t\tflg = cur_row_sum == row_sum;\n\t\t\t\t}\n\t\t\t\tif(!flg) continue; // row with different sum was found\n\t\t\t\t\n\t\t\t\t// check if all columns have same sum\n\t\t\t\tfor(int i{1}, cur_col_sum{0}; i < sz && flg; i++, cur_col_sum=0) {\n\t\t\t\t\tfor(int j = 0; j < sz; j++) \n\t\t\t\t\t\tcur_col_sum += grid[row + j][col + i];\n\t\t\t\t\tflg = cur_col_sum == col_sum;\n\t\t\t\t}\n\t\t\t\tif(!flg) continue; // col with different sum was found\n\t\t\t\treturn sz; // every sum was found to be same and thus this is largest magic sqaure in given matrix\n\t\t\t}\n\t\t\n\treturn 1;\n}\n```\n\n

NOTE

\n\t\t\nIt turns out, we **don\'t actually need to check all the column sums in the above code** and just checking all rows, diagonals and 1st column is enough. It passes all the tests but I haven\'t verified if this is always true. Here\'s the modified code -\n\n```\nint largestMagicSquare(vector>& grid) {\n\tint m = size(grid), n = size(grid[0]);\n\tfor(int sz = min(m, n); sz > 1; sz--) \n\t\tfor(int row{}; row <= m - sz; row++) \n\t\t\tfor(int col{}; col <= n - sz; col++) { \n\t\t\t\tint row_sum{}, col_sum{}, diag_sum{}, diag2_sum{}; \n bool flg = true;\n\t\t\t\tfor(int i{}; i < sz; i++) \n row_sum += grid[row][col + i], col_sum += grid[row + i][col], \n\t\t\t\t diag_sum += grid[row + i][col + i], diag2_sum += grid[row + i][col + (sz-1) - i]; \n\t\t\t\tif(diag_sum != diag2_sum || diag_sum != row_sum || diag_sum != col_sum) continue;\n\t\t\t\tfor(int i{1}; i < sz && flg; i++) \n\t\t\t\t\tfor(int j{}, cur_row_sum{0}; j < sz; j++) \n\t\t\t\t\t\tflg = (cur_row_sum += grid[row + i][col + j]) == row_sum;\n\t\t\t\tif(flg) return sz;\n\t\t\t}\n\treturn 1;\n}\n```\n\n

\n\n***Time Complexity :*** **`O(min(M,N)^5)`**\n***Space Complexity :*** **`O(1)`**\n\n---\n\n\u2714\uFE0F ***Solution - II (Using Prefix-Sums)***\n\nWe cant reduce the time complexity by using prefix sums of each row, column, diagonal and anti-diagonal of the matrix. This will allow us to calculate the sum of any of these in `O(1)` time.\n\n```\nint largestMagicSquare(vector>& grid) {\n\tint m = size(grid), n = size(grid[0]);\n vector> ROW_SUMS(grid), COL_SUMS(grid), DIAG_SUMS(grid), DIAG2_SUMS(grid);\n for(int row = 0; row < m; row++) \n for(int col = 0; col < n; col++) {\n if(col - 1 >= 0) ROW_SUMS[row][col] += ROW_SUMS[row][col - 1];\n if(row - 1 >= 0) COL_SUMS[row][col] += COL_SUMS[row - 1][col];\n if(row - 1 >= 0 && col - 1 >= 0) DIAG_SUMS[row][col] += DIAG_SUMS[row - 1][col - 1];\n if(row - 1 >= 0 && col + 1 < n) DIAG2_SUMS[row][col] += DIAG2_SUMS[row - 1][col + 1];\n }\n \n\tfor(int sz = min(m, n); sz > 1; sz--) // start from max-sized square\n\t\tfor(int row = 0; row <= m - sz; row++) // iterate over all starting row index for sqaure of side=sz\n\t\t\tfor(int col = 0; col <= n - sz; col++) { // iterate over all starting col index for sqaure of side=sz\n bool flg = true;\n\t\t\t\t// check if sum of both diagonals of current square is equal\n int diag_sum = DIAG_SUMS[row + sz-1][col + sz-1] - (row - 1 >= 0 && col - 1 >= 0 ? DIAG_SUMS[row-1][col-1] : 0),\n anti_diag_sum = DIAG2_SUMS[row + sz-1][col] - (row - 1 >= 0 && col + sz < n ? DIAG2_SUMS[row-1][col+sz] : 0);\n if(diag_sum != anti_diag_sum) flg = false;\n\t\t\t\t// check if sum of all rows and columns are equal -- reduced to O(sz) from O(sz^2) in previous approach\n for(int i = 0; flg && i < sz; i++) \n if(diag_sum != ROW_SUMS[row + i][col + sz-1] - (col - 1 >= 0 ? ROW_SUMS[row + i][col - 1] : 0) || \n diag_sum != COL_SUMS[row + sz-1][col + i] - (row - 1 >= 0 ? COL_SUMS[row - 1][col + i] : 0)) flg = false;\n if(flg) return sz; // flg hasn\'t been reset meaning all row/col/diag sums are equal, so return current size \n\t\t\t}\n\treturn 1; \n}\n```\n\n***Time Complexity :*** **`O(min(M,N)^4)`**\n***Space Complexity :*** **`O(M*N)`**\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---

Largest Magic Square

Problem Description

Problem Description

Answer Panel