Heap with explanation and time complexity
Initially the heap contains all cells on the perimeter of the map.  Because it is ordered in increasing height, the first cell popped is the lowest point on the
Initially the heap contains all cells on the perimeter of the map.  Because it is ordered in increasing height, the first cell popped is the lowest point on the outer wall.\nCheck the 4 neighbours, ignoring any already explored (in the heap or have already been popped off the heap) or outside the map.\nIf a newly discovered neighbour is lower than the current cell then water can be added on top of it.  We know the water cannot flow out anywhere because the current cell is the lowest.\nAdd the water to this neighbouring cell (zero if neighbour is higher than cell) and push neighbour with its new height onto the heap.\n\nWe are effectively continually raising the water level, filling in any "holes" as we go.\n\nEvery cell is pushed and popped from the heap, which is O(mn log(mn))\n\nIn Python,\n```\n    def trapRainWater(self, heightMap):\n        if not heightMap or not heightMap[0]:\n            return 0\n            \n        rows, cols = len(heightMap), len(heightMap[0])\n        water = 0\n        q = []\n\n        for r in range(rows):\n            heapq.heappush(q, (heightMap[r][0], r, 0))    \n            heapq.heappush(q, (heightMap[r][cols - 1], r, cols - 1))    \n        for c in range(1, cols - 1):\n            heapq.heappush(q, (heightMap[0][c], 0, c))    \n            heapq.heappush(q, (heightMap[rows - 1][c], rows - 1, c))    \n    \n        visited = {(r, c) for _, r, c in q}\n\n        while q:\n            \n            h, r, c = heapq.heappop(q)\n            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n                r1, c1 = r + dr, c + dc\n                if (r1, c1) not in visited and r1 >= 0 and c1 >= 0 and r1 < rows and c1 < cols:\n                    visited.add((r1, c1))\n                    water += max(0, h - heightMap[r1][c1])\n                    heapq.heappush(q, (max(h, heightMap[r1][c1]), r1, c1))\n                \n        return water\n```
['Python']