'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List

# use tuple here since tuples are immutable and cost fewer memory
# which is a little bit faster than list

class Solution:
    # O(N^2) for S and T
    # With dynamic programming, it is either 0 if grid[r][c] is zero, else it
    # is 1 plus the count of the coordinate in the same direction.
    # If the direction is left and we have a row like 01110110, the 
    # corresponding count values are 01230120
    # For each square, we want dp[r][c] to end up being the minimum of the
    # 4 possible counts.
    def orderOfLargestPlusSign(self, N: int, mines: List[List[int]]) -> int:
        banned = {tuple(mine) for mine in mines}
        dp = [[0] * N for _ in range(N)]
        ans = 0
        
        for r in range(N):
            count = 0
            for c in range(N): # horizontal direction check
                count = 0 if (r,c) in banned else count+1
                dp[r][c] = count
            
            count = 0 # update the dp to make value minimum
            for c in range(N-1, -1, -1):
                count = 0 if (r,c) in banned else count+1
                if count < dp[r][c]: dp[r][c] = count
        
        for c in range(N):
            count = 0
            for r in range(N): # high to low
                count = 0 if (r,c) in banned else count+1
                if count < dp[r][c]: dp[r][c] = count
            
            count = 0 
            for r in range(N-1, -1, -1): # low to high
                count = 0 if (r, c) in banned else count+1
                if count < dp[r][c]: dp[r][c] = count
                if dp[r][c] > ans: ans = dp[r][c]
        
        return ans
        