✅ Simple Trapping Rainwater ✅Beats 100% ✅ Detailed Explanation Solution
Trapping Rain Water in a 2D Grid: Detailed Explanation 🌊Problem Context 🏞️You are given a 2D height map representing an elevation map where each cell's value in
### **Trapping Rain Water in a 2D Grid: Detailed Explanation** 🌊

---

### **Problem Context** 🏞️  
You are given a 2D height map representing an elevation map where each cell's value indicates the height of terrain at that point. The goal is to calculate how much water can be trapped after it rains.

---

### **Core Idea** 🌟  

Water trapped at a cell depends on the minimum boundary height surrounding it.  
- If the cell's height is less than this boundary height, it can hold water.  
- Otherwise, it contributes nothing to the trapped water.

---

### **Approach: Iterative Spreading with Updates** 🔄  

The algorithm uses a dynamic update technique to spread water constraints iteratively. The solution works as follows:

---

### **Steps Explained**

#### **1. Initialization**  
1. Dimensions `m` and `n` of the grid are determined.
2. A `vols` array is initialized to represent the "potential water levels" at each cell, starting with the terrain's height (`heightMap[i][j]`).

---

#### **2. Spreading Water Constraints**  

**Goal:** Update the `vols` grid to ensure water height respects terrain and surrounding constraints.  

- **First Pass (Left-to-Top):**
  - Traverse from the top-left to the bottom-right.
  - Update each cell by ensuring it does not exceed the minimum water level of its top or left neighbors.
  - Adjust the water level to:
    \[
    \text{vols}[i][j] = \max(\text{heightMap}[i][j], \min(\text{vols}[i-1][j], \text{vols}[i][j-1]))
    \]

- **Second Pass (Right-to-Bottom):**
  - Traverse from the bottom-right to the top-left.
  - Update each cell similarly, ensuring it respects constraints from bottom and right neighbors:
    \[
    \text{vols}[i][j] = \max(\text{heightMap}[i][j], \min(\text{vols}[i+1][j], \text{vols}[i][j+1]))
    \]

---

#### **3. Convergence Check**  
If no updates are made during a pass (`upt` remains `false`), the process terminates.  

---

#### **4. Calculate Result**  

- For each cell `(i, j)` inside the boundary, compute trapped water as:
  \[
  \text{res} += \max(0, \text{vols}[i][j] - \text{heightMap}[i][j])
  \]

---

### **Illustrative Example** 📚  

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

#### **Execution Steps:**  

1. **Initialization:**  
   ```
   vols = [
     [1, 4, 3, 1, 3, 2],
     [3, 2, 1, 3, 2, 4],
     [2, 3, 3, 2, 3, 1]
   ]
   ```

2. **Left-to-Top Pass:**  
   Update `vols` based on constraints from top and left neighbors.

3. **Right-to-Bottom Pass:**  
   Adjust `vols` using constraints from right and bottom neighbors.

4. **Final `vols`:**  
   ```
   vols = [
     [1, 4, 3, 1, 3, 2],
     [3, 3, 2, 3, 3, 4],
     [2, 3, 3, 2, 3, 1]
   ]
   ```

5. **Result Calculation:**  
   Trapped water = Sum of differences between `vols` and `heightMap` at each cell:  
   \[
   \text{res} = (3-2) + (3-1) + (3-2) = 4
   \]

---

### **Code Breakdown and Comments** 🧑‍💻

```java
class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length; // Grid rows
        int n = heightMap[0].length; // Grid columns
        
        // Step 1: Initialize volumes with terrain heights
        int[][] vols = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vols[i][j] = heightMap[i][j];
            }
        }

        // Step 2: Iterative spreading to enforce constraints
        boolean upt = true;
        boolean init = true;
        while (upt) {
            upt = false;
            
            // Pass 1: Spread constraints from top-left to bottom-right
            for (int i = 1; i < m - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    int val = Math.max(heightMap[i][j], 
                                       Math.min(vols[i - 1][j], vols[i][j - 1]));
                    if (init || vols[i][j] > val) {
                        vols[i][j] = val;
                        upt = true;
                    }
                }
            }
            init = false;

            // Pass 2: Spread constraints from bottom-right to top-left
            for (int i = m - 2; i >= 1; i--) {
                for (int j = n - 2; j >= 1; j--) {
                    int val = Math.max(heightMap[i][j], 
                                       Math.min(vols[i + 1][j], vols[i][j + 1]));
                    if (vols[i][j] > val) {
                        vols[i][j] = val;
                        upt = true;
                    }
                }
            }
        }

        // Step 3: Calculate total trapped water
        int res = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (vols[i][j] > heightMap[i][j])
                    res += vols[i][j] - heightMap[i][j];
            }
        }
        return res;
    }
}
```

---

### **Complexity Analysis** 📊  

#### **Time Complexity:**  
- **Initialization:** \(O(m \times n)\)  
- **Iterative Spreading:**  
  - Each pass processes every cell → \(O(m \times n)\) per pass.  
  - Number of passes depends on grid size but converges quickly.  

**Overall:** Approx \(O(k \times m \times n)\), where \(k\) is the number of iterations.

#### **Space Complexity:**  
- `vols` grid → \(O(m \times n)\).

---

### **Advantages of the Approach**  
- Simplicity in iterative updates.  
- Effectively handles varying grid shapes and heights.  

['Array', 'Matrix', 'Java']