Most Optimal Solution ✅Beats 100% | C++| Java | Python | JavaScript
⬆️Upvote if it helps ⬆️Connect with me on Linkedin [Bijoy Sing]Solution in C++, Python, Java, and JavaScriptIntuitionThe key insight is to observe that water ca
# ⬆️Upvote if it helps ⬆️

---

## Connect with me on Linkedin [Bijoy Sing]

---

###### *Solution in C++, Python, Java, and JavaScript*
```cpp []
class Solution {
    const int dx[4] = {-1, 0, 1, 0};
    const int dy[4] = {0, 1, 0, -1};
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty() || heightMap[0].empty()) return 0;
        
        const int m = heightMap.size();
        const int n = heightMap[0].size();
        
        priority_queue<pair<int, pair<int, int>>, 
                      vector<pair<int, pair<int, int>>>, 
                      greater<>> pq;
                      
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        for (int j = 0; j < n; j++) {
            pq.push({heightMap[0][j], {0, j}});
            pq.push({heightMap[m-1][j], {m-1, j}});
            visited[0][j] = visited[m-1][j] = true;
        }
        
        for (int i = 1; i < m-1; i++) {
            pq.push({heightMap[i][0], {i, 0}});
            pq.push({heightMap[i][n-1], {i, n-1}});
            visited[i][0] = visited[i][n-1] = true;
        }
        
        int water = 0;
        while (!pq.empty()) {
            auto [height, coords] = pq.top();
            auto [row, col] = coords;
            pq.pop();
            
            for (int k = 0; k < 4; k++) {
                int newRow = row + dx[k];
                int newCol = col + dy[k];
                
                if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || 
                    visited[newRow][newCol]) continue;
                
                if (heightMap[newRow][newCol] < height) {
                    water += height - heightMap[newRow][newCol];
                    pq.push({height, {newRow, newCol}});
                } else {
                    pq.push({heightMap[newRow][newCol], {newRow, newCol}});
                }
                visited[newRow][newCol] = true;
            }
        }
        return water;
    }
};
```
```python []
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        if not heightMap or not heightMap[0]:
            return 0
        
        m, n = len(heightMap), len(heightMap[0])
        heap = []
        visited = [[False] * n for _ in range(m)]
        
        # Direction arrays
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        
        # Add border cells to heap
        for j in range(n):
            heapq.heappush(heap, (heightMap[0][j], 0, j))
            heapq.heappush(heap, (heightMap[m-1][j], m-1, j))
            visited[0][j] = visited[m-1][j] = True
            
        for i in range(1, m-1):
            heapq.heappush(heap, (heightMap[i][0], i, 0))
            heapq.heappush(heap, (heightMap[i][n-1], i, n-1))
            visited[i][0] = visited[i][n-1] = True
            
        water = 0
        while heap:
            height, row, col = heapq.heappop(heap)
            
            for k in range(4):
                new_row, new_col = row + dx[k], col + dy[k]
                
                if (new_row < 0 or new_row >= m or new_col < 0 or new_col >= n or 
                    visited[new_row][new_col]):
                    continue
                    
                if heightMap[new_row][new_col] < height:
                    water += height - heightMap[new_row][new_col]
                    heapq.heappush(heap, (height, new_row, new_col))
                else:
                    heapq.heappush(heap, (heightMap[new_row][new_col], new_row, new_col))
                visited[new_row][new_col] = True
                
        return water
```
```java []
class Solution {
    private final int[] dx = {-1, 0, 1, 0};
    private final int[] dy = {0, 1, 0, -1};
    
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) 
            return 0;
            
        int m = heightMap.length;
        int n = heightMap[0].length;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] - b[0]);
        boolean[][] visited = new boolean[m][n];
        
        // Add border cells
        for (int j = 0; j < n; j++) {
            pq.offer(new int[]{heightMap[0][j], 0, j});
            pq.offer(new int[]{heightMap[m-1][j], m-1, j});
            visited[0][j] = visited[m-1][j] = true;
        }
        
        for (int i = 1; i < m-1; i++) {
            pq.offer(new int[]{heightMap[i][0], i, 0});
            pq.offer(new int[]{heightMap[i][n-1], i, n-1});
            visited[i][0] = visited[i][n-1] = true;
        }
        
        int water = 0;
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int height = curr[0], row = curr[1], col = curr[2];
            
            for (int k = 0; k < 4; k++) {
                int newRow = row + dx[k];
                int newCol = col + dy[k];
                
                if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || 
                    visited[newRow][newCol]) continue;
                    
                if (heightMap[newRow][newCol] < height) {
                    water += height - heightMap[newRow][newCol];
                    pq.offer(new int[]{height, newRow, newCol});
                } else {
                    pq.offer(new int[]{heightMap[newRow][newCol], newRow, newCol});
                }
                visited[newRow][newCol] = true;
            }
        }
        return water;
    }
}
```
```javascript []
class Solution {
    constructor() {
        this.dx = [-1, 0, 1, 0];
        this.dy = [0, 1, 0, -1];
    }
    
    trapRainWater(heightMap) {
        if (!heightMap || !heightMap[0]) return 0;
        
        const m = heightMap.length;
        const n = heightMap[0].length;
        
        const pq = new MinPriorityQueue({ 
            priority: x => x[0] 
        });
        const visited = Array(m).fill().map(() => Array(n).fill(false));
        
        for (let j = 0; j < n; j++) {
            pq.enqueue([heightMap[0][j], 0, j]);
            pq.enqueue([heightMap[m-1][j], m-1, j]);
            visited[0][j] = visited[m-1][j] = true;
        }
        
        for (let i = 1; i < m-1; i++) {
            pq.enqueue([heightMap[i][0], i, 0]);
            pq.enqueue([heightMap[i][n-1], i, n-1]);
            visited[i][0] = visited[i][n-1] = true;
        }
        
        let water = 0;
        while (!pq.isEmpty()) {
            const [height, row, col] = pq.dequeue().element;
            
            for (let k = 0; k < 4; k++) {
                const newRow = row + this.dx[k];
                const newCol = col + this.dy[k];
                
                if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || 
                    visited[newRow][newCol]) continue;
                    
                if (heightMap[newRow][newCol] < height) {
                    water += height - heightMap[newRow][newCol];
                    pq.enqueue([height, newRow, newCol]);
                } else {
                    pq.enqueue([heightMap[newRow][newCol], newRow, newCol]);
                }
                visited[newRow][newCol] = true;
            }
        }
        return water;
    }
}
```

# Intuition
The key insight is to observe that water can only be trapped if a cell is surrounded by higher cells. We can use a min-heap approach starting from the border cells and gradually move inward, keeping track of the minimum height needed to contain water at each step.

# Approach
1. Start from the border cells (which can't trap water) and add them to a min-heap
2. Use a priority queue to process cells from lowest to highest height
3. For each cell, check its unvisited neighbors:
   - If a neighbor is lower, it can trap water up to the current cell's height
   - If a neighbor is higher, use its original height
4. Keep track of visited cells to avoid cycles
5. Continue until all cells are processed

# Complexity
- Time complexity: $$O(mn \log(mn))$$ where m×n is the size of the grid
  - Each cell is pushed/popped from the priority queue once
  - Each operation on priority queue takes log(mn) time
- Space complexity: $$O(mn)$$
  - For the visited array and priority queue

### *If you have any questions or need further clarification, feel free to drop a comment! 😊*
['Array', 'Matrix', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']