🔥🔥||easy to learn solution||Beats 100% in most||With proof||☕💎✅➕💡🖥️🐍#️⃣||🔥🔥
Hello, pls upvote if you upvote my solution
I will upvote your solution too. Just write your username in the comments.Intuition 🌟The problem involves finding th
![beats 100% .png](https://assets.leetcode.com/users/images/4fcef6a5-99ae-48a6-bfdd-edf223b531f3_1737259424.560509.png)

**Hello, pls upvote if you upvote my solution 
I will upvote your solution too. Just write your username in the comments.**


---


---


# Intuition 🌟 
The problem involves finding the amount of water that can be trapped in a 2D grid of elevations. Each cell has a height, and water can only accumulate if it is surrounded by higher elevations.
The key insight is:

- The amount of water trapped above a cell depends on the minimum boundary height around that cell.
- By processing boundary cells first and moving inward, we ensure that the boundary heights for each cell are accurately computed.

---


---


# Approach🚀
- **Treat the elevation map as a grid, where each cell has a height.**
- **Use a min-heap to simulate the process of water filling the grid:**
    1. Start by adding all boundary cells to the heap since they form the initial "walls" of the container.
    1. Mark these boundary cells as visited to prevent revisiting them.
- **Process the heap:**
1. Pop the cell with the minimum height from the heap.
1. For each of its unvisited neighbors, calculate the water trapped:
1. If the height of the current cell is greater than the neighbor’s height, water is trapped, and the trapped volume is added to the total.
1. Add the neighbor to the heap with a height equal to the maximum of the current cell's height and the neighbor's height.
1. Mark the neighbor as visited.
- **Repeat until the heap is empty.**
- **The total water trapped is the sum of all trapped volumes.**

---


---


# Complexity⌚
- **Time Complexity:**
1. Constructing the graph: O(m * n)
1. Processing all cells using Dijkstra's algorithm: O((m * n) * log(m * n))
1. Overall: O(m * n * log(m * n))
- **Space Complexity:**
1. Graph storage: O(m * n)
1. Priority queue: O(m * n)
1. Overall: O(m * n)

---


---


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

        int rows = heightMap.size(), cols = heightMap[0].size();
        vector<vector<int>> graph(rows * cols + 1);
        int virtualStart = rows * cols;

        // Direction vectors for moving in 4 directions
        vector<int> dx = {0, 0, 1, -1};
        vector<int> dy = {1, -1, 0, 0};

        // Build the graph
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int currentCell = i * cols + j;

                // Connect boundary cells to virtual start node
                if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                    graph[virtualStart].push_back(currentCell);
                }

                // Connect current cell to its neighbors
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < rows && y >= 0 && y < cols) {
                        graph[currentCell].push_back(x * cols + y);
                    }
                }
            }
        }

        // Dijkstra-like BFS to calculate distances
        auto calculateDistances = [&](int start) {
            vector<int> dist(graph.size(), INT_MAX / 2);
            dist[start] = 0;

            // Min-heap to prioritize cells with smaller heights
            set<pair<int, int>> pq; // {distance, node}
            pq.insert({0, start});

            while (!pq.empty()) {
                auto [currentDist, currentNode] = *pq.begin();
                pq.erase(pq.begin());

                for (int neighbor : graph[currentNode]) {
                    int weight = heightMap[neighbor / cols][neighbor % cols];
                    if (max(currentDist, weight) < dist[neighbor]) {
                        pq.erase({dist[neighbor], neighbor});
                        dist[neighbor] = max(currentDist, weight);
                        pq.insert({dist[neighbor], neighbor});
                    }
                }
            }

            return dist;
        };

        vector<int> dist = calculateDistances(virtualStart);

        // Calculate trapped water
        int trappedWater = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int cell = i * cols + j;
                int boundaryHeight = dist[cell];
                if (boundaryHeight > heightMap[i][j]) {
                    trappedWater += boundaryHeight - heightMap[i][j];
                }
            }
        }

        return trappedWater;
    }
};
```
```python3 []
from heapq import heappush, heappop
from typing import List

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])
        visited = [[False] * n for _ in range(m)]
        heap = []
        
        # Add all boundary cells to the heap
        for i in range(m):
            for j in [0, n - 1]:
                heappush(heap, (heightMap[i][j], i, j))
                visited[i][j] = True
        
        for j in range(n):
            for i in [0, m - 1]:
                heappush(heap, (heightMap[i][j], i, j))
                visited[i][j] = True
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        trapped_water = 0
        while heap:
            height, x, y = heappop(heap)
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    trapped_water += max(0, height - heightMap[nx][ny])
                    heappush(heap, (max(height, heightMap[nx][ny]), nx, ny))
                    visited[nx][ny] = True
        
        return trapped_water
```
```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;
    }
}
```
```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
```
```rust []
use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
    pub fn trap_rain_water(h: Vec<Vec<i32>>) -> i32 {
        let n = h.len();
        let m = h[0].len();
        let mut level = vec![vec![i32::MAX; m];n];
        let mut q = BinaryHeap::new();
        for i in 0..n {
            for &j in &[0, m-1] {
                level[i][j] = h[i][j];
                q.push((Reverse(level[i][j]), i, j))
            }
        }
        for j in 1..m-1 {
            for &i in &[0, n-1] {
                level[i][j] = h[i][j];
                q.push((Reverse(level[i][j]), i, j))
            }
        }
        while let Some((Reverse(x), i, j)) = q.pop() {
            let ip = i + 1;
            let im = i.wrapping_sub(1);
            let jp = j + 1;
            let jm = j.wrapping_sub(1);
            for &(ii,jj) in &[(ip, j), (im, j), (i,jp), (i,jm)] {
                if ii < n && jj < m && level[ii][jj] == i32::MAX {
                    level[ii][jj] = x;
                    q.push((Reverse(x.max(h[ii][jj])), ii, jj))
                }
            }
        }
        let mut total = 0;
        for i in 0..n {
            for j in 0..m {
                total += (level[i][j] - h[i][j]).max(0)
            }
        }
        total
    }
}
```
```swift []
import Algorithms
import Collections
class Solution {
    struct HeapItem:Comparable {
        let x,y,z:Int
        static func <(l:Self,r:Self)->Bool {l.z < r.z}
    }
    func trapRainWater(_ heights: [[Int]]) -> Int {
        let (rows, cols) = (heights.count, heights[0].count)
        let borders = chain(
            (0..<rows).lazy.flatMap {y in [(0,y),(cols-1,y)]},
            (0..<cols).lazy.flatMap {x in [(x,0),(x,rows-1)]}
        )
        var heap = Heap(borders.map{x,y in HeapItem(x:x, y:y, z:heights[y][x]) })
        var visited = Array(repeating: false, count: cols*rows)
        borders.forEach {x,y in visited[y*cols + x] = true}
        var count = 0

        while let item = heap.popMin() {
            for (dx,dy) in [0,1,0,-1,0].adjacentPairs() {
                let (x,y) = (item.x + dx, item.y + dy)
                guard
                    0..<rows ~= y, 0..<cols ~= x,
                    !visited[y*cols + x]
                else { continue }
                heap.insert(HeapItem(x:x, y:y, z:max(heights[y][x], item.z)))
                visited[y*cols + x] = true
                count += max(0, item.z - heights[y][x])
            }
        }
        return count
    }
}
```
```C# []

public class Solution {
    class Point{
        public int x;
        public int y;
        public int val;
        public Point(int _x,int _y,int _val){
            x = _x;
            y=_y;
            val = _val;
        }
    }
    public int TrapRainWater(int[][] heightMap) {
        int m = heightMap.Length, n = heightMap[0].Length;
        PriorityQueue<Point,int> pq = new(Comparer<int>.Create((a, b) => a.CompareTo(b)));
        // add boundry
        for(int r = 0; r < m;r++){
            pq.Enqueue(new Point(r,0,heightMap[r][0]),heightMap[r][0]);
            pq.Enqueue(new Point(r,n - 1,heightMap[r][n - 1]),heightMap[r][n - 1]);
            heightMap[r][n - 1] = -1;
            heightMap[r][0] = -1;
        }
        for(int c = 1; c < n - 1;c++){
            pq.Enqueue(new Point(0,c,heightMap[0][c]),heightMap[0][c]);
            pq.Enqueue(new Point(m - 1,c,heightMap[m - 1][c]),heightMap[m - 1][c]);
            heightMap[0][c] = -1;
            heightMap[m - 1][c] = -1;
        }

        Tuple<int,int>[] dir = new Tuple<int,int>[]
        {Tuple.Create(0,1), Tuple.Create(0,-1),Tuple.Create(1,0),Tuple.Create(-1,0)};
        int res = 0;
        while(pq.Count > 0){
            var boundary = pq.Dequeue();
            for(int i = 0;i < dir.Length;i++){
                int x = boundary.x + dir[i].Item1, y = boundary.y + dir[i].Item2;
                if(x < 0 || x >= m || y < 0 || y >= n || heightMap[x][y] == -1) continue;
                res+= Math.Max(0,boundary.val - heightMap[x][y]);
                Point newBoundary = new Point(x,y,Math.Max(   heightMap[x][y], boundary.val  ));
                pq.Enqueue(newBoundary,newBoundary.val);
                heightMap[x][y] = -1;
            }
        }

        return res;
    }
}
```
```C []
#define ppi pair<int,pair<int,int>>
Solution {
public:
  
  int DR[4]={1,0,-1,0};
  int DC[4]={0,1,0,-1};

int trapRainWater(vector<vector<int>>& heightMap) {
     int n=heightMap.size();
     int m=heightMap[0].size();

    priority_queue<ppi,vector<ppi>,greater<ppi>> pq;
    vector<vector<bool>>vis(n,vector<bool>(m,false));
    
    for(int i=0;i<n;i++){           
        for(int j=0;j<m;j++){
            if(i==0 || j==0 || i==n-1 || j==m-1){
			    pq.push({heightMap[i][j] , {i,j}}) ;
				vis[i][j]=true;
			}
        }
    }
       
    int total=0;
    int minBdht=0;        
    while(!pq.empty())       
    {
        int currHeight = pq.top().first;
        int x=pq.top().second.first;
        int y=pq.top().second.second;
        pq.pop();
        
        minBdht = max( currHeight , minBdht);
        
      
        
        for(int i=0;i<4;i++)
        {
            int newX = x+DR[i];
            int newY = y+DC[i];
            
            if(newX>=0 && newX<n && newY>=0 && newY<m && !vis[newX][newY] )  // edgecase of bfs
            {
                   pq.push({heightMap[newX][newY] , {newX , newY}});
                   vis[newX][newY]=true;
                   if(heightMap[newX][newY] < minBdht)
                   {
                       total += (minBdht-heightMap[newX][newY]); 
                   }              
            }
            
        }
        
    }
    return total;
}
};
```
```php []
class Solution {

    /**
     * @param Integer[][] $heightMap
     * @return Integer
     */
    function trapRainWater($heightMap) {
        if (empty($heightMap)) return 0;
        
        $m = count($heightMap);
        $n = count($heightMap[0]);
        $pq = new SplPriorityQueue();
        $visited = array_fill(0, $m, array_fill(0, $n, false));
        $dirs = [[-1,0],[1,0],[0,-1],[0,1]];
        $res = 0;
        
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($i == 0 || $i == $m - 1 || $j == 0 || $j == $n - 1) {
                    $pq->insert([$i, $j, $heightMap[$i][$j]], -$heightMap[$i][$j]);
                    $visited[$i][$j] = true;
                }
            }
        }
        
        while (!$pq->isEmpty()) {
            $cell = $pq->extract();
            $h = $cell[2];
            $i = $cell[0];
            $j = $cell[1];
            
            foreach ($dirs as $dir) {
                $x = $i + $dir[0];
                $y = $j + $dir[1];
                
                if ($x >= 0 && $x < $m && $y >= 0 && $y < $n && !$visited[$x][$y]) {
                    $visited[$x][$y] = true;
                    $res += max(0, $h - $heightMap[$x][$y]);
                    $pq->insert([$x, $y, max($h, $heightMap[$x][$y])], -max($h, $heightMap[$x][$y]));
                }
            }
        }
        
        return $res;
    }
}

$solution = new Solution();
$heightMap1 = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]];
echo $solution->trapRainWater($heightMap1); // Output: 4
$heightMap2 = [[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]];
echo $solution->trapRainWater($heightMap2); // Output: 10
```
```javascript []
/**
create minheap consisting of all borders

while heap not empty
  take min
  search each direction
  if not visited
    if depth lower than waterline
      add diff to total
    add to visited
    add to heap
return total
 */

const trapRainWater = map => {
    const heap = createMinHeap()
    const visited = new Set()
    let total = 0
    let waterline = 0
    
    // add borders
    const endj = map[0].length - 1
    const endi = map.length - 1
    for ( let i = 1; i < endi; i++ ) {
        visited.add( i )
        visited.add( i + .1 / endj)
        heap.add([ i, 0, map[i][0] ])
        heap.add([ i, endj, map[i][endj] ])
    }
    for ( let j = 1; j < endj; j++ ) {
        visited.add( .1 / j )
        visited.add( endi + .1 / j)
        heap.add([ 0, j, map[0][j] ])
        heap.add([ endi, j, map[endi][j] ])
    }
    
    // by working at the min border and moving in
    // its known that any depth below waterline will pool
    while ( heap.size() ) {
        const [ i, j, d ] = heap.takeMin()
        waterline = Math.max( waterline, d )
        
        dirs( i, j ).forEach( ([ di, dj ]) => {
            const key = di + .1 / dj
            if ( visited.has( key ) || di <= 0 || dj <= 0 || di >= endi || dj >= endj ) return
            visited.add( key )
            var newd = map[ di ][ dj ]
            
            if ( newd < waterline ) {
                total += waterline - newd
            }
            
            heap.add([ di, dj, newd ])
        })
    }
    
    return total
}

const createMinHeap = () => {
    const heap = [null]
    const leftChild = x => x * 2
    const rightChild = x => x * 2 + 1
    const parent = x => Math.floor( x / 2 )

    return {
        heap,
        size: () => heap.length - 1,
        takeMin: () => {
            if ( heap.length === 2 ) return heap.pop()
            const min = heap[1]
            const last = heap.length - 1
            let l, r, c, index = 1
            
            // swap w/ last in arr && pop
            heap[1] = heap.pop()

            // percolate down
            while ( index < last ) {
                l = leftChild( index )
                r = rightChild( index )
                c = heap[r] && heap[r][2] < heap[l][2] ? r : l

                if ( heap[c] && heap[c][2] < heap[index][2] ) {
                    let hold = heap[c]
                    heap[c] = heap[index]
                    heap[index] = hold
                    index = c
                } else {
                    break
                }
            }
            
            while ( ! heap[ heap.length - 1 ] ) heap.pop()
            return min
        },
        add: tile => {
            // push to end
            let pi, index = heap.length
            
            // percolate up until parent <= tile
            while ( 1 < index ) {
                pi = parent( index )
                
                if ( heap[ pi ] && heap[ pi ][2] <= tile[2] ) break

                heap[ index ] = heap[ pi ]
                index = pi
            }
            heap[ index ] = tile
            
            while ( ! heap[ heap.length - 1 ] ) heap.pop()
        }
    }
}

const dirs = ( i, j ) => [ [ i + 1, j ], [ i - 1, j ], [ i, j + 1 ], [ i, j - 1 ] ]
```
```ruby []
def trap_rain_water(height_map)
    Solution.new(height_map).call
end

class Solution 
    attr_reader :queue, :board

    DIRECTIONS = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    def initialize(height_map)
        @queue = Queue.new
        @board = Board.new(height_map)
    end

    def call
        initialize_start_state

        current_height = 0
        result = 0

        while queue.any?
            item = queue.shift

            if item.height < current_height
                result += current_height - item.height
            else
                current_height = item.height
            end

            DIRECTIONS.each do |d_row, d_col|
                board.process(item.row + d_row, item.col + d_col) do |i, j, value|
                    queue.add(i, j, value)
                end
            end
        end

        result
    end

    private

    def initialize_start_state
        board.initial_cells do |row, col, height|
            queue.add(row, col, height)
        end
    end
end

class Board
    def initialize(board)
        @board = board
        @height = board.length
        @width = board.first.length

        @tracked = Array.new(height) do
            Array.new(width)
        end
    end

    def process(row, col)
        if row >= 0 && col >= 0 && row < height && col < width && !tracked[row][col]
            tracked[row][col] = true
            yield row, col, board[row][col]
        end
    end

    def initial_cells(&block)
        height.times do |row|
            process(row, 0, &block)
            process(row, width - 1, &block)
        end

        width.times do |col|
            process(0, col, &block)
            process(height - 1, col, &block)
        end
    end

    private

    attr_reader :board, :tracked, :height, :width
end

class Queue
    Item = Struct.new(:row, :col, :height)

    def initialize
        @store = []
    end

    def add(row, col, height)
        item = Item.new(row, col, height)

        index = store.bsearch_index { |i| i.height > height } || store.length
        store.insert(index, item)
    end

    def shift
        store.shift
    end

    def any?
        store.any?
    end

    private

    attr_reader :store
end
```
![plez upvote.png](https://assets.leetcode.com/users/images/d38d73b8-fdff-41e5-8d95-1832c74fb19f_1737259699.5084648.png)

['Swift', 'C', 'Python', 'C++', 'Java', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']