#1895
Largest Magic Square
pupil · 535 · lc medium +28 · premium · verified · 75.3% accepted · 609 likes · top 86%
Description
A k x k magic square is a grid where every row sum, column sum, and both diagonal sums are equal (values need not be distinct). A 1 x 1 grid is always magic.
Given an m x n integer grid, return the side length of the largest magic square that can be found within it.
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
Code
1
2
3