<p>A <code>k x k</code> <strong>magic square</strong> is a <code>k x k</code> grid filled with integers such that every row sum, every column sum, and both diagonal sums are <strong>all equal</strong>. The integers in the magic square <strong>do not have to be distinct</strong>. Every <code>1 x 1</code> grid is trivially a <strong>magic square</strong>.</p>

<p>Given an <code>m x n</code> integer <code>grid</code>, return <em>the <strong>size</strong> (i.e., the side length </em><code>k</code><em>) of the <strong>largest magic square</strong> that can be found within this grid</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/29/magicsquare-grid.jpg" style="width: 413px; height: 335px;" />
<pre>
<strong>Input:</strong> grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/29/magicsquare2-grid.jpg" style="width: 333px; height: 255px;" />
<pre>
<strong>Input:</strong> grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 50</code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        # k x k magic square is a grid filled with integers such that every row sum, col sum, and both diagonal sums are equal
        
        # return largest magic square in the grid

        # m, n == 50 at most

        # super brute force: for all top-left locations and all k: O(m n min(m, n)) choices
        # do the brute force check in O(k**2)
        #
        # for O(m n min(m, n)**3) = 50**5 = 5**5 e5 = 3125e5: TLE

        # speed up the check to O(k) by storing row and column sums: O(m n min(m, n)**2) for 625e4 = 6e6 ops. barely within TLE

        # speed up more: for each `k` we can record the number of consecutive items with the same col sum we saw while scanning across each row
        #     if the number is k then, and only then, should we check the k rows. otherwise we know it can't work
        #     in this way most grids will have O(m n min(m, n)) work done

        R = len(grid)
        C = len(grid[0])

        rowSums = [row[:] for row in grid]
        colSums = [row[:] for row in grid]

        for r in range(R):
            for c in range(1, C):
                rowSums[r][c] += rowSums[r][c-1]

        for c in range(C):
            for r in range(1, R):
                colSums[r][c] += colSums[r-1][c]

        def hasMagicSquare(k: int) -> bool:
            # strategy:
            #     for a magic square with upper-left and (r, c)
            #         r:r+k must sum to the same value for all columns in c:c+k
            #         so in each row we can start by getting the cumulative number of
            #         elements matching the same col sum among c:c+k
            #             iff it's k exactly do we proceed and check rows

            # to get consecutive counts we can scan across from left to right
            # so we're really scanning the top-right of the box. NBD.
            for r in range(R-k+1):
                prev = 0
                consec = 0
                for c in range(C):
                    colsum = colSums[r+k-1][c] - (colSums[r-1][c] if r else 0)
                    if colsum == prev:
                        consec += 1
                    else:
                        prev = colsum
                        consec = 1

                    if consec > k: consec -= 1 # only situation where we need to drop the left element is if it's part of the same run

                    if consec == k:
                        # possible magic square
                        if all((rowSums[rr][c] - (rowSums[rr][c-k] if c >= k else 0)) == prev for rr in range(r, r+k)):
                            # check diagonals
                            if sum(grid[r+d][c-k+1+d] for d in range(k)) == prev and sum(grid[r+d][c-d] for d in range(k)) == prev:
                                return True

            return False # no magic square of this size

        # trick from other solutions: return first k > 1 we find a magic square for, that's the largest
        for k in range(min(R, C)+1, 1, -1):
            if hasMagicSquare(k): return k

        return 1
149