Python | O(mn log(mn)) | Heap Explained
The idea is to set the height of the water at the boundary and work our way inwards.\nFirst, set the the (water) height of all boundary points to their heightMa
The idea is to set the height of the water at the boundary and work our way inwards.\nFirst, set the the (water) height of all boundary points to their `heightMap` values, then iteratively choose the lowest boundary point and set its neighbors. To choose the lowest, we maintain a min heap containing the boundary coordinates, with priority given by their (water) height.\n\n\n```python\nimport heapq\n\n\nclass Solution:\n    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n        m = len(heightMap)\n        n = len(heightMap[0])\n        \n        # initialize heap containing boundary points\n        heights = {}\n        heap = []\n        for r in range(m):\n            for c in range(n):\n                if r == 0 or r == m - 1 or c == 0 or c == n - 1:\n                    h = heightMap[r][c]\n                    heights[(r, c)] = h\n                    heapq.heappush(heap, (h, (r, c)))\n        \n        # set height of neighbors for the lowest boundary point at each step\n        total = 0\n        while len(heap) > 0:\n            _, (r, c) = heapq.heappop(heap)\n            for r_o, c_o in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:\n                if 0 <= r_o < m and 0 <= c_o < n and (r_o, c_o) not in heights:\n                    h = max(heights[(r, c)], heightMap[r_o][c_o])\n                    heights[(r_o, c_o)] = h\n                    total += h - heightMap[r_o][c_o]\n                    heapq.heappush(heap, (h, (r_o, c_o)))\n        return total\n```
['Python']