Python BFS + Minheap with explanation
\n# Solution Logic: MinHeap+BFS\n# 1. Start from the boundary elements\n# 2. Maintain a minheap of heights \n# 3. Maintain a a set of visited elements\n# 4. pus
```\n# Solution Logic: MinHeap+BFS\n# 1. Start from the boundary elements\n# 2. Maintain a minheap of heights \n# 3. Maintain a a set of visited elements\n# 4. push all outer boundary elements to the minheap\n# 5. while minheap is not empty:\n#     pop the element from minheap\n#     check all 4 neighbors \n#             check if neoighbor is in bounds of the grid i.e isValid and check if it is not visited\n#             calculate if element height is greater than the neighbor\n#             if yes, add the diff to result and ADD THE NEIGHBOR WITH UPDATED HEIGHT EQUAL TO CURRENT ELEMENT HEIGHT TO MINHEAP\n#             else ADD THE NEIGHBOR TO MINHEAP with no change in its height\n#             mark the neighbor as visited by adding it to the visited set\n        \n# NOTE: few important points:\n# 1. why we use minheap: because we need to process low heights first as they will be able to make water flow out of the grid. if we start with max ones, then we might have wrong result coz the neighbors will be reached in incorrect order.\n# 2. why BFS: layer by layer exploration of neighbors helps get optimal answer\n\n\nimport heapq\nclass Solution:\n    def trapRainWater(self, h: List[List[int]]) -> int:\n            \n        q=[]\n        heapq.heapify(q)\n        visited=set()\n        \n        def isValid(m,n):\n            if 0<=m<r and 0<=n<c:\n                return True\n            return False\n        \n        r=len(h)\n        c=len(h[0])\n        \n        for i in range(r):\n            for j in range(c):\n                if i==0 or i==r-1 or j==0 or j==c-1:\n                    heapq.heappush(q,(h[i][j],i,j))\n                    visited.add((i,j))\n        res=0\n        while q:\n            cur=heapq.heappop(q)\n            \n            for d in [(-1,0),(1,0),(0,-1),(0,1)]:\n                new_i=cur[1]+d[0]\n                new_j = cur[2]+d[1]\n                if isValid(new_i, new_j) and (new_i, new_j) not in visited:\n                    h_inc=max(0,cur[0]-h[new_i][new_j])\n                    res+=h_inc\n                    if h_inc>0:\n                        heapq.heappush(q,(cur[0],new_i, new_j))\n                    else:\n                         heapq.heappush(q,(h[new_i][new_j],new_i, new_j))\n                    visited.add((new_i, new_j))\n        return res\n\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Python', 'Python3']