💯⚠✅BFS Traversal Very Easy Explanation With Example Walkthroughs.✅⚠💯
IntuitionThe problem, Trapping Rain Water II, is a 2D extension of the classic "Trapping Rain Water" problem. Instead of a one-dimensional array, we now have a
### Intuition

The problem, **Trapping Rain Water II**, is a 2D extension of the classic "Trapping Rain Water" problem. Instead of a one-dimensional array, we now have a 2D grid (height map). Each cell represents the height of a block, and water can be trapped in the lower areas surrounded by taller blocks.

The key insight is to recognize that water can only be trapped up to the height of the shortest boundary around a cell. This naturally leads to using a **min-heap** to keep track of the boundary's smallest height during the simulation. The process involves:

1. Treating the boundary cells as the initial boundary.
2. Expanding the boundary inward while updating the trapped water volume.

---

### Approach (Detailed Explanation)

1. **Initial Setup**:
   - **Boundary Initialization**: 
     - Start by marking all the boundary cells (first and last rows, first and last columns). These cells can't trap water but serve as the initial boundary.
     - Push all boundary cells into a **min-heap** based on their height.
   - **Visited Set**:
     - Maintain a set of visited cells to ensure that each cell is processed only once.

2. **Processing the Min-Heap**:
   - The **min-heap** ensures that the smallest height boundary cell is processed first. This is important because water trapping depends on the shortest boundary height.
   - Pop the smallest height cell from the heap. This cell represents the current boundary.

3. **Expand to Neighboring Cells**:
   - For each neighbor of the current cell:
     - If the neighbor is within bounds and not visited:
       - Calculate the amount of water trapped above the neighbor:
         - **Water Trapped** = maxHeight - height of the neighbor.
         - **maxHeight**: The maximum height seen so far (ensures no water spills over).
       - Update the total volume of trapped water.
       - Push the neighbor into the heap with its height.
       - Mark the neighbor as visited.

4. **Continue Until the Heap is Empty**:
   - Keep expanding the boundary until all cells are visited.
   - The total volume of trapped water is updated incrementally.

5. **Return the Total Volume**:
   - The accumulated volume gives the total water trapped.

---

### Key Observations

- **Boundary Cells**:
  - Boundary cells themselves cannot trap water because there is no higher boundary around them.
- **Min-Heap**:
  - The min-heap ensures that we always process the smallest boundary height first, which guarantees that no water spills over before being accounted for.
- **Water Trapping Logic**:
  - Water trapped above a cell is determined by the difference between the boundary height and the cell’s height. Negative values (no trapping) are automatically handled by taking the maximum with 0.

---
### Visual Explanation with Example

Let’s go step by step using an example to understand the approach with diagrams.

#### Example Input:
```plaintext
heightMap = [
  [1, 4, 3, 1, 3, 2],
  [3, 2, 1, 3, 2, 4],
  [2, 3, 3, 2, 3, 1]
]
```

---

### Step 1: Initialize Min-Heap with Boundary Cells

We first add all boundary cells to the **min-heap**. Boundary cells can’t trap water, but they form the initial "fence" for the trapping process. The heap will store tuples in the form `(height, row, col)`.

**Boundary Cells Added to Heap:**
```plaintext
[(1, 0, 0), (4, 0, 1), (3, 0, 2), (1, 0, 3), (3, 0, 4), (2, 0, 5),
 (3, 1, 0),                         (4, 1, 5),
 (2, 2, 0), (3, 2, 1), (3, 2, 2), (2, 2, 4), (1, 2, 5)]
```

---

### Step 2: Process Min-Heap

We start processing the heap. The heap ensures that we always process the **shortest height** first. This guarantees that no water is trapped incorrectly.

#### Diagram of Initial Setup:
Here’s the initial height map with boundary cells marked as part of the heap:
```plaintext
1   4   3   1   3   2  (Boundary)
3       ?   ?   ?       4
2   ?   ?   ?   ?   1  (Boundary)
```

- \( ? \): These cells are to be processed.
- **Visited Cells**: Boundary cells are marked as visited.

---

#### Step 3: Process Each Cell

1. **Pop Cell from Min-Heap**:
   - Start with the cell with the smallest height. In this case, `(1, 0, 0)` is the smallest.

2. **Check Neighbors**:
   - For each neighbor (up, down, left, right), calculate the potential water trapped:
     - Water Trapped = max(0, maxHeight - neighborHeight)
   - Update the heap and visited cells.

---

#### Example Walkthrough

1. **First Cell**: (1, 0, 0)  
   - **Neighbors**: (1, 1, 0)
     - Height: \( 3 \), Water Trapped: \( max(0, 1 - 3) = 0 \).

   - Update Heap:
     ```plaintext
     [(3, 1, 0), (4, 0, 1), ..., (3, 2, 1)]
     ```

---

### Step 4: Iteratively Update

The process continues until the heap is empty. Below is a series of diagrams showing how the heap and the trapped water update.

---

#### After Processing Several Steps:
**Updated Height Map:**
```plaintext
1   4   3   1   3   2
3   2   2   2   3   4
2   3   3   2   3   1
```

**Trapped Water**:  
Each cell now either has its height updated (from trapped water) or remains unchanged.

---

### Final Example

Let’s consider the total trapped water. In this case, the total volume is calculated by summing the trapped water in each cell.

**Final Volume Trapped**:
- Total Trapped Water = \( 4 \).

---

### Diagram Summary:

1. **Heap Initialization**:
   - Start with the boundary cells.
2. **Expand Boundary**:
   - Gradually expand inward by processing the smallest height first.
3. **Trapped Water**:
   - Calculate water trapped at each step based on the difference between the boundary and cell height.

This method guarantees correctness and efficiency by focusing on local boundaries and minimizing redundant calculations. Let me know if you’d like step-by-step diagrams for a specific case!

### Complexity Analysis

#### Time Complexity
- **Heap Operations**:
  - Pushing and popping from the heap takes \( O(\log(k)) \), where \( k \) is the size of the heap.
  - Since each cell is added to the heap once, the total time is \( O((m \times n) \log(m \times n)) \), where \( m \) is the number of rows and \( n \) is the number of columns.
- **Neighbor Processing**:
  - Each cell has at most 4 neighbors, so this is \( O(m \times n) \).

**Overall Time Complexity**: \( O((m \times n) \log(m \times n)) \).

#### Space Complexity
- **Heap**: Stores all boundary cells, so \( O(m \times n) \).
- **Visited Set**: Stores visited cells, \( O(m \times n) \).

**Overall Space Complexity**: \( O(m \times n) \).

---



# Code
```python3 []
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        def valid(r, c):
            return r >= 0 and r < m and c >= 0 and c < n and (r, c) not in visited
    

        m, n = len(heightMap), len(heightMap[0])
        neighbourCells = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        visited = set()
        minHeap = []
        for i in range(m):
            for j in range(n):
                if i in [0, m - 1] or j in [0, n - 1]:
                    heapq.heappush(minHeap, (heightMap[i][j], i, j))
                    visited.add((i, j))

        
        volume, maxHeight = 0, 0

        while minHeap:
            curHeight, r, c = heapq.heappop(minHeap)
            maxHeight = max(maxHeight, curHeight)
            volume += maxHeight - curHeight

            for x, y in neighbourCells:
                newR, newC = r + x, y + c
                if valid(newR, newC):
                    heapq.heappush(minHeap, (heightMap[newR][newC], newR, newC))
                    visited.add((newR, newC))

        return volume
```
```Java []
import java.util.*;

class Solution {
    public int minCost(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Deque<int[]> queue = new ArrayDeque<>();
        Map<String, Integer> visited = new HashMap<>();
        
        queue.addFirst(new int[]{0, 0, 0});
        visited.put("0,0", 0);
        
        while (!queue.isEmpty()) {
            int[] current = queue.pollFirst();
            int r = current[0], c = current[1], cost = current[2];
            
            if (r == n - 1 && c == m - 1) return cost;

            for (int move = 1; move <= 4; move++) {
                int x = moves[move - 1][0], y = moves[move - 1][1];
                int newR = r + x, newC = c + y;
                int newCost = cost + (grid[r][c] == move ? 0 : 1);
                
                String key = newR + "," + newC;
                if (newR >= 0 && newR < n && newC >= 0 && newC < m 
                    && newCost < visited.getOrDefault(key, Integer.MAX_VALUE)) {
                    visited.put(key, newCost);
                    if (grid[r][c] == move) {
                        queue.addFirst(new int[]{newR, newC, newCost});
                    } else {
                        queue.addLast(new int[]{newR, newC, newCost});
                    }
                }
            }
        }
        
        return -1; // Should not reach here
    }
}

```
```C++ []
#include <vector>
#include <deque>
#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        deque<array<int, 3>> queue;
        unordered_map<string, int> visited;
        
        queue.push_front({0, 0, 0});
        visited["0,0"] = 0;

        while (!queue.empty()) {
            auto [r, c, cost] = queue.front();
            queue.pop_front();

            if (r == n - 1 && c == m - 1) return cost;

            for (int move = 1; move <= 4; move++) {
                int x = moves[move - 1][0], y = moves[move - 1][1];
                int newR = r + x, newC = c + y;
                int newCost = cost + (grid[r][c] == move ? 0 : 1);
                
                string key = to_string(newR) + "," + to_string(newC);
                if (newR >= 0 && newR < n && newC >= 0 && newC < m 
                    && (visited.find(key) == visited.end() || newCost < visited[key])) {
                    visited[key] = newCost;
                    if (grid[r][c] == move) {
                        queue.push_front({newR, newC, newCost});
                    } else {
                        queue.push_back({newR, newC, newCost});
                    }
                }
            }
        }
        
        return -1; // Should not reach here
    }
};

```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Matrix', 'C++', 'Java', 'Python3']