Greedy | 2-way DP | 10ms
IntuitionThe core idea is greedy:
"Initially set the water level to infinity, then simulate the behavior of water flowing from higher to lower areas, gradually
# Intuition
The core idea is greedy:
>"Initially set the water level to infinity, then simulate the behavior of water flowing from higher to lower areas, gradually draining the excess water."

# Approach

To calculate the total trapped water, we first determine the maximum "water level" at each cell. After computing the water levels, the trapped water for any cell can be obtained as:

$$trappedWater[i][j]=waterLevel[i][j]−heightMap[i][j]$$

> How to calculate the water level?

Here we use a 2-way dynamic programming approach, where we iteratively update water levels from different directions until they stabilize.

If you want to understand the underlying principles and implementation of 2-way DP, you can refer to the ["Approach 1: Dynamic Programming" of 1368. Minimum Cost to Make at Least One Valid Path in a Grid](https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/editorial/?envType=problem-list-v2&envId=2xsdnxsg)


# Example Walkthrough
Input:
5 5 5 5
5 2 2 3
5 2 2 9
5 3 9 9

Initialize `waterLevel` as ∞.
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞


Update the water level of the surrounding walls to the floor height.
(The walls cannot retain any water.)
5 5 5 5
5 ∞ ∞ 3
5 ∞ ∞ 9
5 3 9 9



Simulate water flowing to the left and top, perform Forward Update from left-top to right-bottom:
5 5 5 5
5 5 5 3
5 5 5 9
5 3 9 9

Simulate water flowing to the right and bottom, run Backward update from right-bottom to left-top:
5 5 5 5
5 3 3 3
5 3 5 9
5 3 9 9

Perform Forward Update again:
5 5 5 5
5 3 3 3
5 3 3 9
5 3 9 9

It's not changed after another round of Baward Update, so we can terminate the update process.

Subtract `heightMap` from the stabilized `waterLevel` to get the trapped water:
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0 


# Code
```java []
class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        int[][] waterLevel = new int[m][n];
        int sum = 0;

        initWaterLevel(waterLevel, heightMap);

        // Iterate until water levels stabilize
        while (true) {
            boolean hasChanged = false;

            // Forward pass (Assume the water flows towards the top-left.)
            for (int i = 1; i < m - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    int oldValue = waterLevel[i][j];
                    waterLevel[i][j] = Math.max(
                        heightMap[i][j],
                        Math.min(waterLevel[i][j], Math.min(waterLevel[i - 1][j], waterLevel[i][j - 1]))
                    );
                    if (waterLevel[i][j] != oldValue) hasChanged = true;
                }
            }

            if (!hasChanged) break;
            hasChanged = false; 

            // Backward pass (Assume the water flows towards the bottom-right.)
            for (int i = m - 2; i >= 1; i--) {
                for (int j = n - 2; j >= 1; j--) {
                    int oldValue = waterLevel[i][j];
                    waterLevel[i][j] = Math.max(
                        heightMap[i][j],
                        Math.min(waterLevel[i][j], Math.min(waterLevel[i + 1][j], waterLevel[i][j + 1]))
                    );
                    if (waterLevel[i][j] != oldValue) hasChanged = true;
                }
            }

            if (!hasChanged) break;
        }

        // Calculate trapped water
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                sum += waterLevel[i][j] - heightMap[i][j];
            }
        }

        return sum;
    }

    private void initWaterLevel(int[][] waterLevel, int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;

        // Initialize waterLevel as ∞
        for (int i = 0; i < m; i++) {
            Arrays.fill(waterLevel[i], Integer.MAX_VALUE);
        }

        // Update the water level of the surrounding walls to the floor height.
        for (int i = 0; i < m; i++) {
            waterLevel[i][0] = heightMap[i][0];
            waterLevel[i][n - 1] = heightMap[i][n - 1];
        }

        for (int j = 0; j < n; j++) {
            waterLevel[0][j] = heightMap[0][j];
            waterLevel[m - 1][j] = heightMap[m - 1][j];
        }
    }
}


```
```kotlin []
class Solution {
    fun trapRainWater(heightMap: Array<IntArray>): Int {
        val m = heightMap.size
        val n = heightMap[0].size
        val waterLevel = Array(m) { IntArray(n) { Int.MAX_VALUE } }
        var sum = 0

        initWaterLevel(waterLevel, heightMap)

        while (true) {
            var hasChanged = false

            // Forward pass (Assume the water flows towards the top-left.)
            for (i in 1..m - 2) {
                for (j in 1..n - 2) {
                    val oldValue = waterLevel[i][j]
                    waterLevel[i][j] = minOf(
                        waterLevel[i][j],
                        waterLevel[i - 1][j],
                        waterLevel[i][j - 1]
                    ).coerceAtLeast(heightMap[i][j])
                    if (waterLevel[i][j] != oldValue) hasChanged = true
                }
            }

            if (!hasChanged) break
            hasChanged = false

            // Backward pass (Assume the water flows towards the bottom-right.)
            for (i in m - 2 downTo 1) {
                for (j in n - 2 downTo 1) {
                    val oldValue = waterLevel[i][j]
                    waterLevel[i][j] = minOf(
                        waterLevel[i][j],
                        waterLevel[i + 1][j],
                        waterLevel[i][j + 1]
                    ).coerceAtLeast(heightMap[i][j])
                    if (waterLevel[i][j] != oldValue) hasChanged = true
                }
            }

            if (!hasChanged) break
        }

        for (i in 1..m - 2) {
            for (j in 1..n - 2) {
                sum += waterLevel[i][j] - heightMap[i][j]
            }
        }

        return sum
    }

    private fun initWaterLevel(waterLevel: Array<IntArray>, heightMap: Array<IntArray>) {
        val m = heightMap.size
        val n = heightMap[0].size

        // Update the water level of the surrounding walls to the floor height.
        for (i in 0 until m) {
            waterLevel[i][0] = heightMap[i][0]
            waterLevel[i][n - 1] = heightMap[i][n - 1]
        }

        for (j in 0 until n) {
            waterLevel[0][j] = heightMap[0][j]
            waterLevel[m - 1][j] = heightMap[m - 1][j]
        }
    }
}

```

# Complexity
Assume `k` is the number of times forward/backward updates are performed.
- Time Complexity: $$O(m*n*k)$$ 
In the worst case (when the water needs to flow through multiple zigzag paths to drain out of the walls.), k will be `O(M*N)`, but this kind of input is very rare, so k is usually quite small.
- Space Complexity: $$O(m*n)$$


['Dynamic Programming', 'Greedy', 'Java', 'Kotlin']