# Trapping Rain Water II
**Difficulty:** HARD
[External](https://leetcode.com/problems/trapping-rain-water-ii)
Canonical: https://scaleengineer.com/dsa/problems/trapping-rain-water-ii
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [X](https://scaleengineer.com/companies/x), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Otter.ai](https://scaleengineer.com/companies/otter.ai)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/trapping-rain-water-ii/image0.jpg) 

**Input:** heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
**Output:** 4
**Explanation:** After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.

**Example 2:**

![](https://assets.glich.co/dsa/trapping-rain-water-ii/image1.jpg) 

**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

**Constraints:**

* `m == heightMap.length`
* `n == heightMap[i].length`
* `1 <= m, n <= 200`
* `0 <= heightMap[i][j] <= 2 * 104`

# Approaches
## Brute Force: Dijkstra from Each Cell
This approach directly tackles the problem by considering each interior cell one by one. For every cell, it calculates the maximum water level it can hold. This level is determined by the 'weakest link' in the surrounding walls, which corresponds to the path to the boundary with the minimum possible maximum height. A search algorithm, similar to Dijkstra's, is executed from each interior cell to find this minimum wall height. The trapped water for that cell is then the wall height minus the cell's own height. Summing this up for all cells gives the total volume.
**Time:** O(M² * N² * log(MN)). We iterate through approximately `M*N` interior cells. For each cell, we run a search that, in the worst case, visits all `M*N` cells, with each step involving a priority queue operation of `log(MN)`. This results in a very high time complexity. · **Space:** O(M*N). Each run of the Dijkstra-like search requires a priority queue and a visited matrix, both of which can scale up to the size of the grid.
**Pros:** Conceptually straightforward as it directly models the physical constraint for each individual cell.
**Cons:** Extremely inefficient due to its nested nature (iterating all cells and running a grid search for each).; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
### Explanation
The fundamental idea is to compute the trapped water on a per-cell basis. The water trapped in a cell `(r, c)` is `water_level - heightMap[r][c]`. The `water_level` is constrained by the height of the 'container' walls around it. Water can escape to the boundary, so the `water_level` at `(r, c)` is determined by the lowest possible barrier on a path from `(r, c)` to the edge of the grid. We need to find a path that minimizes the maximum height encountered along it.

This min-max path problem can be solved using Dijkstra's algorithm. For each interior cell `(r, c)`, we perform a search. The 'distance' in our search is not the path length, but the maximum height seen on the path so far. We use a min-priority queue to always expand the path with the smallest maximum height. When the search first reaches any boundary cell, we have found the minimum possible wall height for our starting cell `(r, c)`. We then calculate the trapped water and add it to our total.

```java
// This approach is too slow and will likely time out.
// It's provided for conceptual understanding.
class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
            return 0;
        }
        int m = heightMap.length;
        int n = heightMap[0].length;
        int totalWater = 0;

        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                totalWater += findWaterForCell(i, j, m, n, heightMap);
            }
        }
        return totalWater;
    }

    private int findWaterForCell(int r, int c, int m, int n, int[][] heightMap) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[][] visited = new boolean[m][n];
        
        pq.offer(new int[]{heightMap[r][c], r, c});
        // Note: A true Dijkstra would use a distance matrix, but for simplicity
        // and since we only need the final result, a visited set suffices.
        // A cell is only visited once we are sure we process it with its min-max path height.

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            int h = cell[0];
            int row = cell[1];
            int col = cell[2];

            if(visited[row][col]) continue;
            visited[row][col] = true;

            if (row == 0 || row == m - 1 || col == 0 || col == n - 1) {
                return Math.max(0, h - heightMap[r][c]);
            }

            for (int[] dir : dirs) {
                int nr = row + dir[0];
                int nc = col + dir[1];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                    int newHeight = Math.max(h, heightMap[nr][nc]);
                    pq.offer(new int[]{newHeight, nr, nc});
                }
            }
        }
        return 0; // Should not be reached for a valid grid
    }
}
```
### Algorithm
1. Initialize `totalWater` to 0.
2. Iterate through each interior cell `(r, c)` of the `heightMap`.
3. For each cell, determine the amount of water it can trap. This requires finding the height of the lowest possible wall that can contain water at this cell.
4. The wall height is the minimum of the maximum heights of all possible paths from the cell `(r, c)` to the grid's boundary.
5. To find this wall height, run a Dijkstra-like algorithm starting from `(r, c)`:
    a. Use a min-priority queue to store `(path_max_height, row, col)`.
    b. Initialize the queue with `(heightMap[r][c], r, c)`.
    c. Explore neighbors, always choosing the path with the minimum `path_max_height`.
    d. The `path_max_height` for a new cell is `max(current_path_max_height, new_cell_height)`.
    e. The first time a path reaches any boundary cell, its `path_max_height` is the wall height for the starting cell `(r, c)`.
6. Calculate the trapped water for cell `(r, c)` as `max(0, wall_height - heightMap[r][c])`.
7. Add this amount to `totalWater`.
8. After checking all interior cells, return `totalWater`.

## Optimized Approach: Priority Queue from Boundary
Instead of checking each cell individually, this optimal approach works from the outside-in. It correctly intuits that the boundary cells of the grid form the initial container for the rainwater. The water level is always limited by the lowest point on the containing wall. By using a min-priority queue, we can always process the cell on the current 'shoreline' that has the minimum height. This simulates the process of water filling up from the lowest points and being contained by an expanding wall of cells.
**Time:** O(M*N * log(MN)). Every cell is added to and removed from the priority queue exactly once. Each priority queue operation takes logarithmic time with respect to its size, which can be up to `M*N`. · **Space:** O(M*N). The space is dominated by the `visited` matrix and the priority queue, which in the worst case can store all `M*N` cells.
**Pros:** This is the most efficient and optimal solution for this problem.; It processes each cell only once, leading to a much better time complexity.; Correctly models the physical process of how a 2D landscape would trap water.
**Cons:** The logic can be less intuitive than a simple brute-force method.; Requires careful implementation of the priority queue logic to ensure correctness.
### Explanation
This efficient solution reframes the problem. We start with the assumption that the grid's boundary cells form the initial wall that contains the water. These cells cannot trap water themselves but define the initial boundary heights. We add all boundary cells to a min-priority queue, which will always give us the lowest point on the current 'wall'.

We then repeatedly extract the minimum-height cell from the queue. This cell's height, say `h`, represents the current water level because it's the lowest point on the boundary from which water could 'leak'. We then look at its unvisited neighbors. For any neighbor, if its height is less than `h`, it will trap `h - neighbor_height` amount of water. This neighbor is then added to our boundary (and the priority queue) to potentially contain more water further inside. The height we add it with is `max(h, neighbor_height)`, because the water level is already established at `h`, and this new cell can only maintain or raise that level.

This process is analogous to a Dijkstra's algorithm starting from all boundary cells simultaneously, where 'distance' is the cell height. It efficiently finds the effective wall height for all interior cells in a single pass over the grid.

```java
class Solution {
    class Cell {
        int row, col, height;
        public Cell(int row, int col, int height) {
            this.row = row;
            this.col = col;
            this.height = height;
        }
    }

    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
            return 0;
        }

        int m = heightMap.length;
        int n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<Cell> pq = new PriorityQueue<>((a, b) -> a.height - b.height);

        // Add all boundary cells to the priority queue
        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) {
                    pq.offer(new Cell(i, j, heightMap[i][j]));
                    visited[i][j] = true;
                }
            }
        }

        int totalWater = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!pq.isEmpty()) {
            Cell cell = pq.poll();
            
            // Explore neighbors
            for (int[] dir : dirs) {
                int r = cell.row + dir[0];
                int c = cell.col + dir[1];

                if (r >= 0 && r < m && c >= 0 && c < n && !visited[r][c]) {
                    visited[r][c] = true;
                    totalWater += Math.max(0, cell.height - heightMap[r][c]);
                    pq.offer(new Cell(r, c, Math.max(cell.height, heightMap[r][c])));
                }
            }
        }

        return totalWater;
    }
}
```
### Algorithm
1. Handle edge cases: If the grid is too small to trap water (less than 3x3), return 0.
2. Create a `visited` matrix of the same dimensions as `heightMap`, initialized to `false`.
3. Create a min-priority queue to store cells as `[row, col, height]`, ordered by `height`.
4. Add all boundary cells of the `heightMap` to the priority queue and mark them as `visited`.
5. Initialize `totalWater = 0`.
6. While the priority queue is not empty:
    a. Dequeue the cell with the minimum height. Let this be `cell` with height `h`.
    b. This `h` represents the current lowest point on the container's wall, effectively the current water level.
    c. For each unvisited neighbor of `cell`:
        i. Mark the neighbor as `visited`.
        ii. Calculate the trapped water at the neighbor: `max(0, h - neighbor_height)`. Add this to `totalWater`.
        iii. Add the neighbor to the priority queue. Its effective height as a new wall element is `max(h, neighbor_height)`. This ensures the water level does not decrease.
7. Return `totalWater`.

# Solutions
### Java

```java
class Solution {
public
  int trapRainWater(int[][] heightMap) {
    if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0)
      return 0;
    int rows = heightMap.length, columns = heightMap[0].length;
    boolean[][] visited = new boolean[rows][columns];
    PriorityQueue<Cell> priorityQueue = new PriorityQueue<Cell>();
```

### Python

```python
''' >>> from itertools import pairwise >>> dirs = (-1, 0, 1, 0, -1) >>> pairwise(dirs) <itertools.pairwise object at 0x104dbe470> >>> list(pairwise(dirs)) [(-1, 0), (0, 1), (1, 0), (0, -1)] ''' from heapq import heappush , heappop class Solution : def trapRainWater ( self , heightMap : List [ List [ int ]]) -> int : m , n = len ( heightMap ), len ( heightMap [ 0 ]) vis = [[ False ] * n for _ in range ( m )] # visited pq = [] for i in range ( m ): for j in range ( n ): if i == 0 or i == m - 1 or j == 0 or j == n - 1 : # border enqueue heappush ( pq , ( heightMap [ i ][ j ], i , j )) # default order vis [ i ][ j ] = True ans = 0 dirs = ( - 1 , 0 , 1 , 0 , - 1 ) while pq : h , i , j = heappop ( pq ) for a , b in pairwise ( dirs ): x , y = i + a , j + b if x >= 0 and x < m and y >= 0 and y < n and not vis [ x ][ y ]: ans += max ( 0 , h - heightMap [ x ][ y ]) # look for neighbour which is lower than pop result hight vis [ x ][ y ] = True heappush ( pq , ( max ( h , heightMap [ x ][ y ]), x , y )) return ans ############ class Solution ( object ): def trapRainWater ( self , heightMap ): """ :type heightMap: List[List[int]] :rtype: int """ if not heightMap : return 0 h = len ( heightMap ) w = len ( heightMap [ 0 ]) ans = 0 heap = [] visited = set () for j in range ( w ): heapq . heappush ( heap , ( heightMap [ 0 ][ j ], 0 , j )) heapq . heappush ( heap , ( heightMap [ h - 1 ][ j ], h - 1 , j )) visited |= {( 0 , j ), ( h - 1 , j )} for i in range ( h ): heapq . heappush ( heap , ( heightMap [ i ][ 0 ], i , 0 )) heapq . heappush ( heap , ( heightMap [ i ][ w - 1 ], i , w - 1 )) visited |= {( i , 0 ), ( i , w - 1 )} dirs = [( 0 , - 1 ), ( 0 , 1 ), ( - 1 , 0 ), ( 1 , 0 )] while heap : height , i , j = heapq . heappop ( heap ) for di , dj in dirs : ni , nj = i + di , j + dj if 0 <= ni < h and 0 <= nj < w and ( ni , nj ) not in visited : ans += max ( 0 , height - heightMap [ ni ][ nj ]) heapq . heappush ( heap , ( max ( heightMap [ ni ][ nj ], height ), ni , nj )) # update new hight, max(heightMap[ni][nj], height) visited |= {( ni , nj )} return ans
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/trapping-rain-water-ii/ // Time: O(MNlog(MN)) // Space: O(MN) // Ref: https://discuss.leetcode.com/topic/60914/concise-c-priority_queue-solution class Solution { typedef array < int , 3 > Point ; public: int trapRainWater ( vector < vector < int >>& A ) { int M = A . size (), N = A [ 0 ]. size (), dirs [ 4 ][ 2 ] = { { 0 , 1 },{ 0 , - 1 },{ 1 , 0 },{ - 1 , 0 } }, ans = 0 , maxH = INT_MIN ; priority_queue < Point , vector < Point > , greater <>> pq ; vector < vector < bool >> seen ( M , vector < bool > ( 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 ) { pq . push ({ A [ i ][ j ], i , j }); seen [ i ][ j ] = true ; } } } while ( pq . size ()) { auto [ h , x , y ] = pq . top (); pq . pop (); maxH = max ( maxH , h ); for ( auto & [ dx , dy ] : dirs ) { int a = x + dx , b = y + dy ; if ( a < 0 || a >= M || b < 0 || b >= N || seen [ a ][ b ]) continue ; seen [ a ][ b ] = true ; if ( A [ a ][ b ] < maxH ) ans += maxH - A [ a ][ b ]; pq . push ({ A [ a ][ b ], a , b }); } } return ans ; } };
```