[Python] 2d dp (n3) to (n2) & binary search
intuition of binary search\ntransfer the mines map into\nrow [[-1,N], [-1,2,N],[-1,3,7,N]...]\ncolomn\nwhich means that in row 2,we have 2 mines on [2,3] and [2
intuition of binary search\ntransfer the mines map into\nrow [[-1,N], [-1,2,N],[-1,3,7,N]...]\ncolomn\nwhich means that in row 2,we have 2 mines on [2,3] and [2,7]\nso if we are considering the length of one arm of a plus sign at [2,5]\nit should be (7-3)/2 horizontally\n```\nclass Solution:\n    def orderOfLargestPlusSign(self, N: int, mines: List[List[int]]) -> int:\n        maxOrder = 0\n        zeros = set((i,j) for i,j in mines)\n        dp = [[0]*N for _ in range(N)]\n        for i in range(N):\n            # ->\n            count = 0\n            for j in range(N):\n                count = 0 if (i,j) in zeros else count + 1\n                dp[i][j] = count\n            # <-\n            count = 0\n            for j in range(N-1,-1,-1):\n                count = 0 if (i,j) in zeros else count + 1\n                dp[i][j] = min(dp[i][j],count)\n        for j in range(N):\n            # ^\n            count = 0\n            for i in range(N):\n                count = 0 if (i,j) in zeros else count + 1\n                dp[i][j] = min(dp[i][j],count)\n            # v\n            count = 0\n            for i in range(N-1,-1,-1):\n                count = 0 if (i,j) in zeros else count + 1\n                dp[i][j] = min(dp[i][j],count)\n                maxOrder = max(dp[i][j],maxOrder)\n                if maxOrder == (N+1)//2:\n                    return maxOrder\n        return maxOrder\n                    \n                    \n```
[]