Share my novel solution with horizontal scanning (No heap used)
I didn\'t check other posts when first solving this problem. After my solution got AC, I checked the discussions and found no similar solution (most people use 
I didn\'t check other posts when first solving this problem. After my solution got AC, I checked the discussions and found no similar solution (most people use heap). This approach is quite intuitive. After a few optimization, it can beat 90%.\n\n**Intuition**\nThe basic idea is to horizontally scan the whole building blocks, from the bottom to the top. At each scan, we compute the area that can hold water. Then step by step, the total volumn accumulates by `area*(h - h_prev)`, where `h`is the current height and `h_prev`is previous height which is a bit lower.\n\nNow the difficult part would be how to compute the area with water at each level. My solution is to use DFS (BFS also works, we only care about reachability). From each edge cell, spreading through the map to see whether an inner cell is reachable from the outside. If an inner cell is horizontally reachable from the edge, it certainlly cannot hold water.\n\n**Implementation details**\nI first sort all the heights, so that we can scan bottom-top. Then we maintain a `m x n` matrix named`level`, which is the scanned profile at a certain height. There are 3 distinct values in `level`: `1` means that this cell is concrete (for current height); `0` means that this cell can hold water; `-1` means that this cell can only hold air (that water would leak from here). And `area` would be the number of `0`s at each level.\n\nOn the ground level, certainly there are only `1` in `level`, and that is how we initialize. As the height gradually rising, `0` occurs. However, if this `0` is at edge or is adjacent to another known leaking cell, it should also be marked `-1`. Further more, other cells that previously can hold water may no longer hold water at this height, so we should DFS to find all leaking cells. Once a position is marked "leaking", it will always "leak" at a higher height. When we reach the top, there are only `-1` in `level`.\n\n**Complexity Analysis**\nTime complexity would be *O*(*mn*log(*mn*)) for the sorting. The iteration would cost *O*(*mn*) since DFS would only visit each cell once (or checking maximum 4 times from adjacent cells) and accumulating volumn costs constant at each level (*mn* levels in total). Space complexity would be *O*(*mn*).\n```\nclass Solution:\n    def trapRainWater(self, heightMap: List[List[int]]) -> int:\n        m, n = len(heightMap), len(heightMap[0])\n        if m < 3 or n < 3: return 0\n        # to simplify the code\n        def adjacent(i,j):\n            return [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]\n        \n        # first we sort all heights from the matrix and store their corresponding positions\n        # heights will be [(h1,[p1, p2,...]), (h2,[p1, p2, ...]), ...]\n        d = defaultdict(list)\n        for i in range(m):\n            for j in range(n):\n                d[heightMap[i][j]].append((i,j))\n        heights = sorted(d.items())\n        # initialization\n        volumn, area, h_lower = 0, 0, heights[0][0]\n        level = [[1 for j in range(n)] for i in range(m)]\n        for h, positions in heights:\n            volumn += area*(h-h_lower)\n            h_lower = h\n            leak = []\n            for i, j in positions:\n                # due to height rising, now this position may hold water\n                level[i][j] = 0\n                area += 1\n                if i == 0 or i == m-1 or j == 0 or j == n-1 or any([level[a][b] == -1 for a, b in adjacent(i,j)]):\n                    # this position is reachable from outside, therefore cannot hold water\n                    leak.append((i,j))\n                    level[i][j] = -1\n                    area -= 1\n            while leak:\n                i, j = leak.pop()\n                for a, b in adjacent(i,j):\n                    if 0 <= a < m and 0 <= b < n and not level[a][b]:\n                        # new leaking position found through DFS\n                        leak.append((a,b))\n                        level[a][b] = -1\n                        area -= 1\n\n        return volumn\n    \n```\nPlease upvote if you like.:-)
['Python3']