Trapping Rain Water II

Master this topic with zero to advance depth.

Trapping Rain Water II

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Visual Representation

heightMap =
[1, 4, 3, 1, 3, 2]
[3, 2, 1, 3, 2, 4]
[2, 3, 3, 2, 3, 1]

Water trapped at (1,1) (height 2): bounded by 3, 4, 3, 3. Can hold 1 unit.
Water trapped at (1,2) (height 1): bounded by 3, 2, 3, 3. Can hold 2 units.
Total trapped = 14 units.

Min-Heap expanding from boundaries:
Push all boundary cells to Min-Heap.
Always pop the lowest boundary (weakest link) to see if water can flow into its neighbors.

Hard

Examples

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 14

Input: heightMap = [[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]]
Output: 10

Approach 1

Level I: Iterative Water Level Updates

Intuition

The water level at any cell (r, c) is determined by the maximum of its own height and the minimum water level of its neighbors. We can start by assuming every inner cell can hold infinite water, and boundary cells hold exactly their height. Then, we iteratively relax (update) the inner cells until the water levels stabilize (no more changes occur), similar to the Bellman-Ford algorithm.

⏱ O((M*N)^2) in the worst-case because we might need to iterate through the entire matrix M*N times until convergence💾 O(M*N) to store the current water levels

Detailed Dry Run

Grid 3x3 (Heights): 3 3 3 3 1 3 3 3 3

Init Water: 3 3 3 3 INF 3 3 3 3

Iter 1: Water[1,1] = max(H[1,1]=1, min(W[0,1]=3, W[2,1]=3, W[1,0]=3, W[1,2]=3)) = max(1, min(3,3,3,3)) = 3 Changes = True. Next loop Changes = False. Trapped at (1,1) = Water[1,1] - H[1,1] = 3 - 1 = 2.

java

public class Main {
    public static int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        int[][] water = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    water[i][j] = heightMap[i][j];
                } else {
                    water[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        int[] dirs = {-1, 0, 1, 0, -1};
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int r = 1; r < m - 1; r++) {
                for (int c = 1; c < n - 1; c++) {
                    int minNeighbor = Integer.MAX_VALUE;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dirs[d], nc = c + dirs[d + 1];
                        minNeighbor = Math.min(minNeighbor, water[nr][nc]);
                    }
                    int newWater = Math.max(heightMap[r][c], minNeighbor);
                    if (newWater < water[r][c]) {
                        water[r][c] = newWater;
                        changed = true;
                    }
                }
            }
        }
        
        int trapped = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                trapped += water[i][j] - heightMap[i][j];
            }
        }
        return trapped;
    }

    public static void main(String[] args) {
        int[][] grid = {{3,3,3},{3,1,3},{3,3,3}};
        System.out.println(trapRainWater(grid)); // 2
    }
}

Approach 2

Level II: 4-Way Boundary Scanning (Upper Bound Heuristic)

Intuition

In the 1D version, the water level at any index is min(maxLeft, maxRight). We can extend this logic to 2D by calculating the maximum height seen from all four cardinal directions (Left, Right, Top, Bottom) for each cell. The water level at (r, c) can be at most the minimum of these four peaks. While this ignores diagonal leaks, it provides an $O(MN)$ heuristic that is faster than iterative relaxation.

⏱ O(M * N) to compute the prefix/suffix maximums in four directions💾 O(M * N) to store the max peaks

Detailed Dry Run

Grid 3x3: 3 3 3 3 1 3 3 3 3 For cell (1,1):

MaxLeft = 3, MaxRight = 3, MaxUp = 3, MaxDown = 3
Level = min(3,3,3,3) = 3
Trapped = 3 - 1 = 2 (Correct in this case).

java

public class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length <= 2) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        int[][] L = new int[m][n], R = new int[m][n], U = new int[m][n], D = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            L[i][0] = heightMap[i][0];
            for (int j = 1; j < n; j++) L[i][j] = Math.max(L[i][j-1], heightMap[i][j]);
            R[i][n-1] = heightMap[i][n-1];
            for (int j = n-2; j >= 0; j--) R[i][j] = Math.max(R[i][j+1], heightMap[i][j]);
        }
        for (int j = 0; j < n; j++) {
            U[0][j] = heightMap[0][j];
            for (int i = 1; i < m; i++) U[i][j] = Math.max(U[i-1][j], heightMap[i][j]);
            D[m-1][j] = heightMap[m-1][j];
            for (int i = m-2; i >= 0; i--) D[i][j] = Math.max(D[i+1][j], heightMap[i][j]);
        }
        
        int ans = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                int minPeak = Math.min(Math.min(L[i][j], R[i][j]), Math.min(U[i][j], D[i][j]));
                ans += Math.max(0, minPeak - heightMap[i][j]);
            }
        }
        return ans;
    }
}

Approach 3

Level III: Min-Heap + BFS (Optimal)

Intuition

Water flows from high places to low places, but its maximum volume is gated by the weakest link (lowest boundary) surrounding it. If we start from the outer boundaries and always process the lowest boundary segment inwards (using a Min-Heap), we simulate how water would spill over. If the neighbor is lower than our current boundary, it fills up with water to meet our boundary height.

⏱ O(MN log MN) because every cell is pushed into and popped out of the Min-Heap once💾 O(MN) for the Min-Heap and visited matrix

Detailed Dry Run

Grid: 3 3 3 3 1 3 3 3 3

Push all boundaries to Min-Heap: (3,0,0),(3,0,1)... Visited boundary.
Pop (3,0,1). Check neighbor (1,1). It's unvisited. Height is 1.
Inner height 1 < Boundary height 3. Trapped = 3 - 1 = 2.
Push neighbor (1,1) into Heap with updated height max(1, 3) = 3, mark visited.
Continue popping. Other neighbors of (1,1) are boundaries and visited. Return total trapped = 2.

java

import java.util.*;

public class Main {
    public static int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[][] visited = new boolean[m][n];
        
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                    minHeap.offer(new int[]{heightMap[r][c], r, c});
                    visited[r][c] = true;
                }
            }
        }
        
        int[] dirs = {-1, 0, 1, 0, -1};
        int trapped = 0, currentMax = Integer.MIN_VALUE;
        
        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int height = curr[0], r = curr[1], c = curr[2];
            currentMax = Math.max(currentMax, height);
            
            for (int d = 0; d < 4; d++) {
                int nr = r + dirs[d], nc = c + dirs[d + 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    if (heightMap[nr][nc] < currentMax) {
                        trapped += currentMax - heightMap[nr][nc];
                    }
                    minHeap.offer(new int[]{heightMap[nr][nc], nr, nc});
                }
            }
        }
        return trapped;
    }

    public static void main(String[] args) {
        int[][] grid = {{3,3,3},{3,1,3},{3,3,3}};
        System.out.println(trapRainWater(grid)); // 2
    }
}

← Previous QuestionSliding Window Maximum

Next Question →Minimum Cost to Hire K Workers

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.