Array | BFS | Priority Queue | Solution for LeetCode#407
IntuitionThe problem of trapping rainwater in a 2D elevation map can be solved using a priority queue and a breadth-first search (BFS) approach. The key insight
![image.png](https://assets.leetcode.com/users/images/77d71897-931a-4fcc-924b-510fc8100ce6_1737274128.079038.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem of trapping rainwater in a 2D elevation map can be solved using a priority queue and a breadth-first search (BFS) approach. The key insight is to start from the boundary and work our way inwards, always processing the lowest height first.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Initialize a priority queue to store cells, ordered by height.
2. Mark all boundary cells as visited and add them to the priority queue.
3. While the priority queue is not empty:
	- Poll the cell with the lowest height.
	- For each unvisited neighboring cell:
		- If the neighbor's height is lower, it can trap water. Add the difference to the total water volume.
		- Add the neighbor to the priority queue with the maximum of its height and the current cell's height.
	- Mark the neighbor as visited.
4. Return the total water volume.

# Complexity
- Time complexity: O(mn log(mn))
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(mn)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {

    public int trapRainWater(int[][] heightMap) {
        int m=heightMap.length;
        int n=heightMap[0].length;
        boolean[][] visited=new boolean[m][n];

        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);

        //Set the boundary element as visited
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 || i==m-1 || j==0 || j==n-1){
                    pq.add(new int[]{heightMap[i][j], i, j});
                    visited[i][j]=true;
                }
            }
        }


        int[][] direction={ {0,1}, {0,-1}, {1,0}, {-1,0} };

        int waterVolume=0;

        //Applying the BFS Traversal
        while(!pq.isEmpty()){
            int[] arr=pq.poll();
            int cv=arr[0];    //Curr value
            int cr=arr[1];    //Curr row
            int cc=arr[2];    //Curr column

            //Visiting the adjacent elemetns of current element
            for(int[] dir:direction){
                int nr=cr+dir[0];   //New row
                int nc=cc+dir[1];   //New column    

                // Checking the element is within row, column and not visited
                if(nr>=0 && nr<m && nc>=0 && nc<n && !visited[nr][nc]){
                    
                    //volume of water it can trap after raining.
                    if(cv-heightMap[nr][nc]>0){
                        waterVolume+=cv-heightMap[nr][nc];
                        pq.add(new int[]{cv, nr, nc});
                    }
                    else{
                        pq.add(new int[]{heightMap[nr][nc], nr, nc});
                    }

                    visited[nr][nc]=true;
                }
                
            }
        }

        return waterVolume;
    }

}             
```
```python []
class Solution(object):
    def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """

        m, n = len(heightMap), len(heightMap[0])
        visited = [[False] * n for _ in range(m)]
        
        pq = []
        
        # Set the boundary elements as visited
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m-1 or j == 0 or j == n-1:
                    heapq.heappush(pq, (heightMap[i][j], i, j))
                    visited[i][j] = True
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        water_volume = 0
        
        # Applying the BFS Traversal
        while pq:
            cv, cr, cc = heapq.heappop(pq)
            
            # Visiting the adjacent elements of current element
            for dr, dc in directions:
                nr, nc = cr + dr, cc + dc
                
                # Checking if the element is within row, column and not visited
                if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                    # Volume of water it can trap after raining
                    if cv - heightMap[nr][nc] > 0:
                        water_volume += cv - heightMap[nr][nc]
                        heapq.heappush(pq, (cv, nr, nc))
                    else:
                        heapq.heappush(pq, (heightMap[nr][nc], nr, nc))
                    
                    visited[nr][nc] = True
        
        return water_volume
        
```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Python', 'Java', 'Python3']