<p>You are given an integer <code>n</code>. You have an <code>n x n</code> binary grid <code>grid</code> with all values initially <code>1</code>&#39;s except for some indices given in the array <code>mines</code>. The <code>i<sup>th</sup></code> element of the array <code>mines</code> is defined as <code>mines[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> where <code>grid[x<sub>i</sub>][y<sub>i</sub>] == 0</code>.</p>

<p>Return <em>the order of the largest <strong>axis-aligned</strong> plus sign of </em>1<em>&#39;s contained in </em><code>grid</code>. If there is none, return <code>0</code>.</p>

<p>An <strong>axis-aligned plus sign</strong> of <code>1</code>&#39;s of order <code>k</code> has some center <code>grid[r][c] == 1</code> along with four arms of length <code>k - 1</code> going up, down, left, and right, and made of <code>1</code>&#39;s. Note that there could be <code>0</code>&#39;s or <code>1</code>&#39;s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for <code>1</code>&#39;s.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/13/plus1-grid.jpg" style="width: 404px; height: 405px;" />
<pre>
<strong>Input:</strong> n = 5, mines = [[4,2]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> In the above grid, the largest plus sign can only be of order 2. One of them is shown.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/13/plus2-grid.jpg" style="width: 84px; height: 85px;" />
<pre>
<strong>Input:</strong> n = 1, mines = [[0,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no plus sign, so return 0.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= mines.length &lt;= 5000</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt; n</code></li>
	<li>All the pairs <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are <strong>unique</strong>.</li>
</ul>



def ConstructMatrix(n, zeroes):
    M = []
    row = [ 1 for i in range(n) ]
    for i in range(n):
        M.append(row.copy())

    for x, y in zeroes:
        M[x][y] = 0
    
    return M

def Accumulate(matrix):
    N = len(matrix)
    M = len(matrix[0])

    S = []

    current = [ 0 for i in range(M) ]
    for row in matrix:
        acc = list(accumulate(row))
        current = [ sum(x) for x in zip(current, acc ) ]
        S.append(current)

    return S

def SubmatrixSum(acc, lx, ly, rx, ry):
    outer = acc[ry][rx]

    inner = acc[ly - 1][lx - 1] if (ly > 0) and (lx > 0) else 0

    upper = acc[ly - 1][rx] if ly > 0 else 0
    left = acc[ry][lx - 1] if lx > 0 else 0

    # print('(%d, %d) - (%d, %d) = [ %d - (%d + %d) - %d ]' % (lx, ly, rx, ry, outer, upper, left, inner))

    return outer - (upper + left) + inner

def FindHorizontalStrips(A, width):
    n = len(A)

    positions = []
    half = width // 2

    for y in range(n):
        for x in range(0, n - width + 1):
            if SubmatrixSum(A, x, y, x + width - 1, y) == width:
                positions.append(tuple([x + half, y]))

    return set(positions)

def Transpose(M):
    T = []
    height = len(M)
    width = len(M[0])
    for i in range(width):
        T.append([ row[i] for row in M])

    return T

def PrintMatrix(M):
    for row in M:
        print(row)

def PlusSignExists(accM, accT, span):
    horizontal = FindHorizontalStrips(accM, span)
    vertical = FindHorizontalStrips(accT, span)

    for x, y in horizontal:
        if tuple([y, x]) in vertical:
            return True

    return False

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        M = ConstructMatrix(n, mines)
        # PrintMatrix(M)

        T = Transpose(M)
        # PrintMatrix(T)

        accM = Accumulate(M)
        accT = Accumulate(T)

        lower_bound = -1
        upper_bound = n // 2

        while lower_bound < upper_bound:
            middle = (lower_bound + upper_bound + 1) // 2

            target = 1 + 2 * middle
            # print(lower_bound, middle, upper_bound)
            if PlusSignExists(accM, accT, target):
                # print('Found plus of size %d' % target)
                lower_bound = middle
            else:
                 # print('No luck for size %d' % target)
                upper_bound = middle - 1

        return 1 + lower_bound

55606