Optimized Water Trapping in 2D Grids Using Priority Queues
IntuitionThe problem requires identifying how much water can be trapped in a 2D elevation map. A naive approach might involve checking all cells repeatedly, but
# Intuition
The problem requires identifying how much water can be trapped in a 2D elevation map. A naive approach might involve checking all cells repeatedly, but an optimized method uses a **priority queue** (min-heap) to simulate the water-filling process. By always processing the smallest boundary first, we ensure that trapped water is computed accurately.

# Approach
1. **Initialization**:
   - Use a priority queue to maintain the current boundary of the water container.
   - Mark all boundary cells as visited and add them to the priority queue.

2. **Processing the Queue**:
   - Poll the smallest height from the queue.
   - For each neighboring cell:
     - If it is not visited:
       - Calculate the trapped water as the difference between the current boundary height and the height of the neighboring cell (if positive).
       - Update the height of the neighboring cell to the maximum of its current height and the boundary height (to maintain a valid boundary).
       - Mark the cell as visited and add it to the queue.

3. **Repeat** until the queue is empty, summing up the trapped water.

# Complexity
- **Time Complexity**:  
  $$O(m \cdot n \cdot \log(m \cdot n))$$  
  - Each cell is processed once and added to the priority queue.
  - The operations on the priority queue take $$O(\log(m \cdot n))$$ time.
  
- **Space Complexity**:  
  $$O(m \cdot n)$$  
  - The space is used for the priority queue and the visited matrix.

# Example Analysis
### Example 1:
Input: `[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]`  
Output: `4`  
Explanation: Water trapped in two regions (1 unit and 3 units).

### Example 2:
Input: `[[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]`  
Output: `10`  
Explanation: Water trapped in the central depression.

# Code
```java []
class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] vis = new boolean[m][n];
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        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.offer(new int[] {heightMap[i][j], i, j});
                    vis[i][j] = true;
                }
            }
        }
        int ans = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        while (!pq.isEmpty()) {
            var p = pq.poll();
            for (int k = 0; k < 4; k++) {
                int x = p[1] + dirs[k], y = p[2] + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
                    ans += Math.max(0, p[0] - heightMap[x][y]);
                    vis[x][y] = true;
                    pq.offer(new int[] {Math.max(p[0], heightMap[x][y]), x, y});
                }
            }
        }
        return ans;
    }
}
```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Matrix', 'C++', 'Java']