764: Memory Beats 91.40%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\ngrid = [[n] * n for _ in range(n)]\n\nWe initialize a grid with all val
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n```\ngrid = [[n] * n for _ in range(n)]\n```\nWe initialize a grid with all values set to n. Why? Because in the best case, if a cell isn\'t blocked (by a mine), its maximum potential reach in any direction is n (from one edge to another).\n\n```\nfor x, y in mines:\n    grid[x][y] = 0\n```\n\nWe then loop through the mines and set those cells to 0 in the grid, as they can\'t be a part of any plus sign.\n\nWe need to determine how far each cell can reach in every direction. This will let us determine the size of the plus sign for which the cell can be a center.\n\n```\nfor i in range(n):\n    l, r, u, d = 0, 0, 0, 0 \n```\n\nWe begin by iterating through each row and column of the matrix using i. For each row and column, we initialize counters for all four directions (left, right, up, down).\n\n```\n            for j in range(n):\n                l = l + 1 if grid[i][j] != 0 else 0\n                r = r + 1 if grid[i][n-j-1] != 0 else 0\n                u = u + 1 if grid[j][i] != 0 else 0\n                d = d + 1 if grid[n-j-1][i] != 0 else 0\n                \n                grid[i][j] = min(grid[i][j], l)\n                grid[i][n-j-1] = min(grid[i][n-j-1], r)\n                grid[j][i] = min(grid[j][i], u)\n                grid[n-j-1][i] = min(grid[n-j-1][i], d)\n```\nWe use another loop with j to traverse through each cell in the row or column. For each cell:\n\nIf the cell isn\'t blocked (i.e., it\'s not a mine), we increment the corresponding counter.\nIf the cell is blocked (i.e., it\'s a mine), we reset the counter to 0 because we can\'t pass through mines.\nWe then update the cell\'s value in the grid to be the minimum of its current value and the counter. This is because the cell\'s value represents the maximum size of the plus sign for which it can be a center, so we\'re continuously refining this estimate.\n\n```\nreturn max(map(max, grid))\n```\n\nFinally, after populating the entire grid with each cell\'s potential as a center of a plus sign, we determine the largest possible plus sign in the grid. This is done by finding the maximum value in the grid.\n\n# Complexity\n- Time complexity:\nO(n^2)\n\n- Space complexity:\nO(n^2)\n\n# Code\n```\nclass Solution:\n    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:\n        grid = [[n] * n for _ in range(n)]\n        \n        for x, y in mines:\n            grid[x][y] = 0\n\n        for i in range(n):\n            l, r, u, d = 0, 0, 0, 0\n            for j in range(n):\n                l = l + 1 if grid[i][j] != 0 else 0\n                r = r + 1 if grid[i][n-j-1] != 0 else 0\n                u = u + 1 if grid[j][i] != 0 else 0\n                d = d + 1 if grid[n-j-1][i] != 0 else 0\n                \n                grid[i][j] = min(grid[i][j], l)\n                grid[i][n-j-1] = min(grid[i][n-j-1], r)\n                grid[j][i] = min(grid[j][i], u)\n                grid[n-j-1][i] = min(grid[n-j-1][i], d)\n        \n        return max(map(max, grid))\n\n```
['Array', 'Dynamic Programming', 'Python', 'Python3']