Python 3 | DP - Bomb Enemy | Explanations
Code is long, but trust me, they are super easy to understand.\n\n### Intuition\n- Brutal force will definitely fail given N can be up to 500 and brutal force i
Code is long, but trust me, they are super easy to understand.\n\n### Intuition\n- Brutal force will definitely fail given N can be up to 500 and brutal force is a `O(N^3)` solution; need to think of something else\n- For a `+` sign, there are 4 directions, up/down/left/right\n\t- If we just check 1 direction in each iteration, and store the value somewhere, then we can reuse the value since it\'s a matrix (we can have previous/next row or column\'s values).\n\t- So we check 4 directions separately, then the time complexity is `O(N^2) * constant = O(N^2)`\n- A `+` should have 4 directions same number of `1`s\n\t- meaning we need to take the minimum of 4 directions\n- Finally, iterate over one more time to find the max\n\n### Explanation\n```\nclass Solution:\n    def orderOfLargestPlusSign(self, N: int, mines: List[List[int]]) -> int:\n        mat = [[1]*N for _ in range(N)]\n        for x, y in mines: mat[x][y] = 0                   # create matrix with mine\n            \n        up = [[0]*N for _ in range(N)]                     # count 1s above mat[i][j] if mat[i][j] is 1\n        for i in range(N):\n            for j in range(N):\n                if mat[i][j]: \n                    up[i][j] = 1\n                    if i > 0: up[i][j] += up[i-1][j] \n                \n        down = [[0]*N for _ in range(N)]                   # count 1s below mat[i][j] if mat[i][j] is 1\n        for i in range(N-1, -1, -1):\n            for j in range(N):\n                if mat[i][j]: \n                    down[i][j] = 1\n                    if i < N-1: down[i][j] += down[i+1][j] \n                    \n        left = [[0]*N for _ in range(N)]                   # count 1s on the left side of mat[i][j] if mat[i][j] is 1\n        for i in range(N):\n            for j in range(N):\n                if mat[i][j]:\n                    left[i][j] = 1\n                    if j > 0: left[i][j] += left[i][j-1]\n                    \n        right = [[0]*N for _ in range(N)]                  # count 1s on the right side of mat[i][j] if mat[i][j] is 1\n        for i in range(N):\n            for j in range(N-1, -1, -1):\n                if mat[i][j]:\n                    right[i][j] = 1\n                    if j < N-1: right[i][j] += right[i][j+1]\n         \n\t\t# find the largest + sign by using cached directions information\n        return max(min([up[i][j], down[i][j], left[i][j], right[i][j]]) for i in range(N) for j in range(N))\n```
['Dynamic Programming', 'Python', 'Python3']