🌟 Min Heap Simplified! 🎯Beginner-Friendly Explanation🧩 + Full Code Breakdown ✨
💡 IntuitionImagine the grid as a landscape of hills and valleys. 🌄 Water can be trapped in valleys, bounded by the minimum boundary height. To figure out how mu
# 💡 Intuition
Imagine the grid as a landscape of hills and valleys. 🌄 Water can be trapped in valleys, bounded by the minimum boundary height. To figure out how much water each cell can trap, we need to know its minimum surrounding height while exploring from the boundaries inward.


---

# 🛠️ Approach
1. 🏗️ Initialize:

    - Create a min-heap (priority queue) to process boundary cells first (as they can’t trap water).
    - Use a visited matrix to ensure cells are processed only once.
2. 🌊 Process Cells:

    - Pop the cell with the smallest height from the heap.
    - Update the maximum height encountered so far.
    - Explore its neighbors (up, down, left, right):
        - If the neighbor is unvisited:
            - Add it to the heap.
            - Calculate trapped water if the neighbor's height is smaller than the maximum height.
3. 🧮 Sum it Up:

    - Keep adding trapped water for all such cells.
    - Continue until all cells are processed.

---

# ⏱️ Complexity
## Time:
    O(n × m × log(n × m)): Each cell is pushed/popped from the heap once, and heap operations are logarithmic.
## Space:
    O(n × m): For the visited matrix and heap storage.

---

# Code
```cpp []
class Solution {
public:
    int trapRainWater(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> vis (n, vector<int> (m, 0));

        auto compare = [&] (auto a, auto b) {
            return get<2> (a) > get<2> (b);
        };
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(compare)> minHeap (compare);

        int maxCurrHeight = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(i == 0 || i == n-1 || j == 0 || j == m-1) {
                    minHeap.push({i, j, grid[i][j]});
                    vis[i][j] = true;
                }
            }
        }

        vector<int> dirRow = {0, 0, 1, -1};
        vector<int> dirCol = {1, -1, 0, 0};

        int vol = 0;

        while(!minHeap.empty()) {
            auto [row, col, height] = minHeap.top();
            minHeap.pop();

            maxCurrHeight = max(maxCurrHeight, height);
            for(int i = 0; i < 4; i++) {
                int nx = row + dirRow[i];
                int ny = col + dirCol[i];

                if(nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny]) {
                    minHeap.push({nx, ny, grid[nx][ny]});
                    vis[nx][ny] = true;
                    if(grid[nx][ny] < maxCurrHeight) {
                        vol += maxCurrHeight - grid[nx][ny];
                    }
                }
            }
        }
        return vol;
    }
};
```
```java []
import java.util.PriorityQueue;

class Solution {
    public int trapRainWater(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] vis = new boolean[n][m];
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int maxCurrHeight = 0, vol = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    minHeap.offer(new int[]{i, j, grid[i][j]});
                    vis[i][j] = true;
                }
            }
        }

        int[] dirRow = {0, 0, 1, -1};
        int[] dirCol = {1, -1, 0, 0};

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

            maxCurrHeight = Math.max(maxCurrHeight, height);

            for (int i = 0; i < 4; i++) {
                int nx = row + dirRow[i];
                int ny = col + dirCol[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    if (grid[nx][ny] < maxCurrHeight) {
                        vol += maxCurrHeight - grid[nx][ny];
                    }
                    minHeap.offer(new int[]{nx, ny, grid[nx][ny]});
                }
            }
        }
        return vol;
    }
}

```
```javascript []
class Solution {
    trapRainWater(grid) {
        const n = grid.length, m = grid[0].length;
        const vis = Array.from({ length: n }, () => Array(m).fill(false));
        const minHeap = new MinHeap();
        let maxCurrHeight = 0, vol = 0;

        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                if (i === 0 || i === n - 1 || j === 0 || j === m - 1) {
                    minHeap.push([grid[i][j], i, j]);
                    vis[i][j] = true;
                }
            }
        }

        const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

        while (!minHeap.isEmpty()) {
            const [height, row, col] = minHeap.pop();
            maxCurrHeight = Math.max(maxCurrHeight, height);

            for (const [dr, dc] of directions) {
                const nx = row + dr, ny = col + dc;
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    if (grid[nx][ny] < maxCurrHeight) {
                        vol += maxCurrHeight - grid[nx][ny];
                    }
                    minHeap.push([grid[nx][ny], nx, ny]);
                }
            }
        }
        return vol;
    }
}

// MinHeap implementation
class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(val) {
        this.heap.push(val);
        this.heap.sort((a, b) => a[0] - b[0]);
    }
    pop() {
        return this.heap.shift();
    }
    isEmpty() {
        return this.heap.length === 0;
    }
}

```
```python []
import heapq

class Solution:
    def trapRainWater(self, grid):
        n, m = len(grid), len(grid[0])
        vis = [[False] * m for _ in range(n)]
        min_heap = []
        max_curr_height = 0
        volume = 0
        
        for i in range(n):
            for j in range(m):
                if i == 0 or i == n-1 or j == 0 or j == m-1:
                    heapq.heappush(min_heap, (grid[i][j], i, j))
                    vis[i][j] = True

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

        while min_heap:
            height, row, col = heapq.heappop(min_heap)
            max_curr_height = max(max_curr_height, height)

            for dr, dc in directions:
                nx, ny = row + dr, col + dc
                if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny]:
                    vis[nx][ny] = True
                    if grid[nx][ny] < max_curr_height:
                        volume += max_curr_height - grid[nx][ny]
                    heapq.heappush(min_heap, (grid[nx][ny], nx, ny))
        
        return volume

```
```ruby []
require 'set'

class Solution
    def trap_rain_water(grid)
        n, m = grid.length, grid[0].length
        vis = Array.new(n) { Array.new(m, false) }
        min_heap = []
        max_curr_height = 0
        volume = 0

        for i in 0...n
            for j in 0...m
                if i == 0 || i == n - 1 || j == 0 || j == m - 1
                    min_heap.push([grid[i][j], i, j])
                    vis[i][j] = true
                end
            end
        end
        min_heap.sort_by! { |x| x[0] }

        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        until min_heap.empty?
            height, row, col = min_heap.shift
            max_curr_height = [max_curr_height, height].max

            directions.each do |dr, dc|
                nx, ny = row + dr, col + dc
                if nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny]
                    vis[nx][ny] = true
                    volume += [max_curr_height - grid[nx][ny], 0].max
                    min_heap.push([grid[nx][ny], nx, ny])
                    min_heap.sort_by! { |x| x[0] }
                end
            end
        end
        volume
    end
end

```
```rust []
use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
    pub fn trap_rain_water(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        let mut vis = vec![vec![false; m]; n];
        let mut min_heap = BinaryHeap::new();
        let mut max_curr_height = 0;
        let mut volume = 0;

        for i in 0..n {
            for j in 0..m {
                if i == 0 || i == n - 1 || j == 0 || j == m - 1 {
                    min_heap.push(Reverse((grid[i][j], i, j)));
                    vis[i][j] = true;
                }
            }
        }

        let directions = [(0, 1), (0, -1), (1, 0), (-1, 0)];

        while let Some(Reverse((height, row, col))) = min_heap.pop() {
            max_curr_height = max_curr_height.max(height);

            for (dr, dc) in directions.iter() {
                let nx = row as isize + dr;
                let ny = col as isize + dc;

                if nx >= 0 && ny >= 0 && nx < n as isize && ny < m as isize {
                    let (nx, ny) = (nx as usize, ny as usize);
                    if !vis[nx][ny] {
                        vis[nx][ny] = true;
                        if grid[nx][ny] < max_curr_height {
                            volume += max_curr_height - grid[nx][ny];
                        }
                        min_heap.push(Reverse((grid[nx][ny], nx, ny)));
                    }
                }
            }
        }
        volume
    }
}

```
```go []
package main

import (
	"container/heap"
)

type Cell struct {
	Height, Row, Col int
}

type MinHeap []Cell

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].Height < h[j].Height }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Cell)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[0 : n-1]
	return item
}

func trapRainWater(grid [][]int) int {
	n, m := len(grid), len(grid[0])
	vis := make([][]bool, n)
	for i := range vis {
		vis[i] = make([]bool, m)
	}

	h := &MinHeap{}
	heap.Init(h)
	maxCurrHeight := 0
	volume := 0

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 || i == n-1 || j == 0 || j == m-1 {
				heap.Push(h, Cell{grid[i][j], i, j})
				vis[i][j] = true
			}
		}
	}

	directions := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

	for h.Len() > 0 {
		cell := heap.Pop(h).(Cell)
		maxCurrHeight = max(maxCurrHeight, cell.Height)

		for _, d := range directions {
			nx, ny := cell.Row+d[0], cell.Col+d[1]
			if nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] {
				vis[nx][ny] = true
				if grid[nx][ny] < maxCurrHeight {
					volume += maxCurrHeight - grid[nx][ny]
				}
				heap.Push(h, Cell{grid[nx][ny], nx, ny})
			}
		}
	}

	return volume
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

```
```c# []
using System;
using System.Collections.Generic;

public class Solution {
    public int TrapRainWater(int[][] grid) {
        int n = grid.Length, m = grid[0].Length;
        bool[,] vis = new bool[n, m];
        var minHeap = new PriorityQueue<(int row, int col, int height), int>();
        int maxCurrHeight = 0, volume = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    minHeap.Enqueue((i, j, grid[i][j]), grid[i][j]);
                    vis[i, j] = true;
                }
            }
        }

        int[] dirRow = { 0, 0, 1, -1 };
        int[] dirCol = { 1, -1, 0, 0 };

        while (minHeap.Count > 0) {
            var (row, col, height) = minHeap.Dequeue();
            maxCurrHeight = Math.Max(maxCurrHeight, height);

            for (int i = 0; i < 4; i++) {
                int nx = row + dirRow[i], ny = col + dirCol[i];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx, ny]) {
                    vis[nx, ny] = true;
                    if (grid[nx][ny] < maxCurrHeight) {
                        volume += maxCurrHeight - grid[nx][ny];
                    }
                    minHeap.Enqueue((nx, ny, grid[nx][ny]), grid[nx][ny]);
                }
            }
        }

        return volume;
    }
}

```
```swift []
import Foundation

class Solution {
    func trapRainWater(_ grid: [[Int]]) -> Int {
        let n = grid.count, m = grid[0].count
        var vis = Array(repeating: Array(repeating: false, count: m), count: n)
        var minHeap = [(Int, Int, Int)]() // (height, row, col)
        var maxCurrHeight = 0, volume = 0

        func heapPush(_ element: (Int, Int, Int)) {
            minHeap.append(element)
            minHeap.sort { $0.0 < $1.0 }
        }

        func heapPop() -> (Int, Int, Int) {
            return minHeap.removeFirst()
        }

        for i in 0..<n {
            for j in 0..<m {
                if i == 0 || i == n - 1 || j == 0 || j == m - 1 {
                    heapPush((grid[i][j], i, j))
                    vis[i][j] = true
                }
            }
        }

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

        while !minHeap.isEmpty {
            let (height, row, col) = heapPop()
            maxCurrHeight = max(maxCurrHeight, height)

            for (dr, dc) in directions {
                let nx = row + dr, ny = col + dc
                if nx >= 0 && ny >= 0 && nx < n && ny < m && !vis[nx][ny] {
                    vis[nx][ny] = true
                    if grid[nx][ny] < maxCurrHeight {
                        volume += maxCurrHeight - grid[nx][ny]
                    }
                    heapPush((grid[nx][ny], nx, ny))
                }
            }
        }

        return volume
    }
}

``` 

['Swift', 'Heap (Priority Queue)', 'Python', 'C++', 'Java', 'Go', 'Rust', 'Ruby', 'JavaScript', 'C#']