407: Time 96.51%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Check for edge cases\nThe function starts by checking if the input hei
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Check for edge cases\nThe function starts by checking if the input height map is empty or has no columns, in which case there is no water that can be trapped and the function returns 0.\n\n2. Initialize variables\nThe function initializes some variables, including the size of the height map (m and n), a visited matrix to keep track of which cells have been processed, an empty heap, and a variable to store the amount of water trapped.\n\n3. Add border cells to heap\nNext, the function adds all the border cells to the heap, along with their heights and coordinates. These are the cells that will be processed first, as they are the ones that can potentially trap water.\n\n4. Process cells in heap\nThe function then enters a loop that processes cells in the heap until there are no more cells left. The loop works as follows:\n\n    - Pop the cell with the lowest height from the heap\n    - Check its neighbors (up, down, left, right) to see if they can be processed\n    - If a neighbor is within the bounds of the height map and has not been visited before, calculate the amount of water that can be trapped in it based on the current highest boundary and the height of the cell, and add it to the total amount of trapped water\n    - Add the neighbor to the heap, with its height updated to the maximum of its original height and the current highest boundary\n    - Mark the neighbor as visited\n\n5. Return amount of trapped water\nOnce all cells in the heap have been processed, the function returns the total amount of trapped water.\n\n# Complexity\n- Time complexity:\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n        if not heightMap or not heightMap[0]:\n            return 0\n        \n        m, n = len(heightMap), len(heightMap[0])\n        visited = [[False]*n for _ in range(m)]\n        heap = []\n        water_trapped = 0\n        \n        # Add all the border cells to the heap\n        for i in range(m):\n            heapq.heappush(heap, (heightMap[i][0], i, 0))\n            heapq.heappush(heap, (heightMap[i][n-1], i, n-1))\n            visited[i][0] = visited[i][n-1] = True\n            \n        for j in range(1, n-1):\n            heapq.heappush(heap, (heightMap[0][j], 0, j))\n            heapq.heappush(heap, (heightMap[m-1][j], m-1, j))\n            visited[0][j] = visited[m-1][j] = True\n            \n        # Process cells in the heap\n        while heap:\n            height, i, j = heapq.heappop(heap)\n            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n                ni, nj = i+di, j+dj\n                if ni >= 0 and ni < m and nj >= 0 and nj < n and not visited[ni][nj]:\n                    visited[ni][nj] = True\n                    water = max(0, height - heightMap[ni][nj])\n                    water_trapped += water\n                    heapq.heappush(heap, (max(heightMap[ni][nj], height), ni, nj))\n        \n        return water_trapped\n\n```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Python', 'Python3']