✅🔥Beats 90%🔥 || 🌧️💧Efficient Implementation of Trapping Rainwater in a 2D Grid Using Min-Heap🛠️
🌊💡 IntuitionThe problem can be visualized as filling water in a 3D elevation map. Imagine the boundaries as walls that hold water, and the height of the walls d
# 🌊💡 Intuition
The problem can be visualized as filling water in a 3D elevation map. Imagine the boundaries as walls that hold water, and the height of the walls determines how much water can be trapped. By using a **priority queue (min-heap)**, we simulate this process, starting from the lowest boundary and working inward, while marking cells as visited to avoid reprocessing.

![Screenshot 2025-01-19 085356.png](https://assets.leetcode.com/users/images/8d032b5f-9b7c-4615-9df0-dcf507f30c1c_1737257390.0464094.png)


# 🛠️🚀 Approach
1. **🏗️ Boundary Initialization**:
   - Add all boundary cells into a **min-heap** with their heights. These boundaries define the limits of water trapping.
   - Mark boundary cells as visited using a 2D array to prevent redundant processing.

2. **📉 Process Cells from the Min-Heap**:
   - Extract the cell with the smallest height from the heap.
   - For each of its **4️⃣ neighboring cells**:
     - Calculate the trapped water:  
       `waterTrapped += max(0, currentHeight - neighborHeight)`.
     - Update the neighbor's height to the larger of its own height or the current height, simulating water filling.
     - Push the updated neighbor into the heap and mark it as visited.

3. **🔁 Repeat Until the Heap is Empty**:
   - Continue the process for all cells in the heap until no more cells are left.

4. **✅ Return the Result**:
   - The accumulated water is returned as the result.

# ⏱️📊 Complexity
- **⏳ Time Complexity**:  
  - Each cell is processed once, and heap operations take \(O(\log(m \times n))\).  
  - Overall complexity: **$$O(m \times n \log(m \times n))$$**.

- **💾 Space Complexity**:  
  - Space is used for the **visited** array and the **min-heap**.  
  - Overall complexity: **$$O(m \times n)$$**.

# UpVote (Cpp, Python, Java)!🤔
![upvote-agree.gif](https://assets.leetcode.com/users/images/7429028c-2f6c-4d2d-a483-816f2e336dce_1737257649.9259944.gif)

# 📝💻 Code
```cpp []
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty() || heightMap[0].empty())
            return 0;

        int m = heightMap.size();
        int n = heightMap[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                       greater<>>
            minHeap;

        // 🚧 Add boundary cells to the minHeap
        for (int i = 0; i < m; ++i) {
            for (int j : {0, n - 1}) {
                minHeap.emplace(heightMap[i][j], i, j);
                visited[i][j] = true;
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int i : {0, m - 1}) {
                if (!visited[i][j]) {
                    minHeap.emplace(heightMap[i][j], i, j);
                    visited[i][j] = true;
                }
            }
        }

        int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int waterTrapped = 0;

        // 🌊🔁 Process cells using the minHeap
        while (!minHeap.empty()) {
            auto [height, x, y] = minHeap.top();
            minHeap.pop();

            for (auto& dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    !visited[nx][ny]) {
                    // 🧮 Calculate water trapped
                    waterTrapped += max(0, height - heightMap[nx][ny]);
                    minHeap.emplace(max(height, heightMap[nx][ny]), nx, ny);
                    visited[nx][ny] = true;
                }
            }
        }

        return waterTrapped; // 🏆 Final result
    }
};
```
``` python []
import heapq

class Solution:
    def trapRainWater(self, heightMap):
        if not heightMap or not heightMap[0]:
            return 0

        m, n = len(heightMap), len(heightMap[0])
        visited = [[False] * n for _ in range(m)]
        minHeap = []

        # Add boundary cells
        for i in range(m):
            for j in [0, n - 1]:
                heapq.heappush(minHeap, (heightMap[i][j], i, j))
                visited[i][j] = True
        for j in range(n):
            for i in [0, m - 1]:
                if not visited[i][j]:
                    heapq.heappush(minHeap, (heightMap[i][j], i, j))
                    visited[i][j] = True

        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        waterTrapped = 0

        while minHeap:
            height, x, y = heapq.heappop(minHeap)

            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    waterTrapped += max(0, height - heightMap[nx][ny])
                    heapq.heappush(minHeap, (max(height, heightMap[nx][ny]), nx, ny))
                    visited[nx][ny] = True

        return waterTrapped
```
``` java []
import java.util.PriorityQueue;

class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0)
            return 0;

        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // Add boundary cells
        for (int i = 0; i < m; ++i) {
            for (int j : new int[]{0, n - 1}) {
                minHeap.offer(new int[]{heightMap[i][j], i, j});
                visited[i][j] = true;
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int i : new int[]{0, m - 1}) {
                if (!visited[i][j]) {
                    minHeap.offer(new int[]{heightMap[i][j], i, j});
                    visited[i][j] = true;
                }
            }
        }

        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int waterTrapped = 0;

        while (!minHeap.isEmpty()) {
            int[] cell = minHeap.poll();
            int height = cell[0], x = cell[1], y = cell[2];

            for (int[] dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    waterTrapped += Math.max(0, height - heightMap[nx][ny]);
                    minHeap.offer(new int[]{Math.max(height, heightMap[nx][ny]), nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }

        return waterTrapped;
    }
}
```
# Why upvote?
1. **Clarity and Readability 📝**  
   Well-structured and easy to follow with clear comments explaining the steps.

2. **Efficiency ⚡**  
   Uses a min-heap to optimize the algorithm and handle large grids efficiently.

3. **Correctness ✅**  
   Accurately calculates trapped water, handling edge cases with proper boundary conditions.

4. **Scalable to Large Inputs 📊**  
   Suitable for competitive programming or real-world applications, scalable for larger 2D grids.




['Heap (Priority Queue)', 'C++', 'Java', 'Python3']