## Algorithm

Problem Name: 407. 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.

Example 1:

```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:

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define DUMP(I, J, K, M, R, C) do { } while (0)
#if 0
int fill(int *ignored, int *visited, int k, int **map, int rowsz, int colsz, int i, int j, int *pm, int *px, int *py) {
int s, x, z, y;
int h, m, w;
​
if (i == 0 || i == rowsz - 1 ||
j == 0 || j == colsz - 1 ||
ignored[i * colsz + j]) {
return -1; // it leaks!
}

if (visited[i * colsz + j] == k) {
return 0;
}

visited[i * colsz + j] = k;

h = map[i][j];

s = map[i - 1][j];            m = s;
x = map[i + 1][j]; if (m > x) m = x;
z = map[i][j - 1]; if (m > z) m = z;
y = map[i][j + 1]; if (m > y) m = y;

w = 0;

if (m > h) {
w = m - h; // multiple drops
*px = i;
*py = j;
} else {
if (w == 0 && m == s) {
w = fill(ignored, visited, k, map, rowsz, colsz, i - 1, j, pm, px, py);
}
if (w == 0 && m == x) {
w = fill(ignored, visited, k, map, rowsz, colsz, i + 1, j, pm, px, py);
}
if (w == 0 && m == z) {
w = fill(ignored, visited, k, map, rowsz, colsz, i, j - 1, pm, px, py);
}
if (w == 0 && m == y) {
w = fill(ignored, visited, k, map, rowsz, colsz, i, j + 1, pm, px, py);
}
}

done:
if (w == -1) {
ignored[i * colsz + j] = -1; // mark leak
} else {
if (w == 0 && *pm > h) {
*pm = h;
*px = i;
*py = j;
}
}

return w;
}
int trapRainWater(int** heightMap, int heightMapRowSize, int heightMapColSize) {
int i, j, k;
int x, y, m;
int w, total;

int *visited = calloc(heightMapRowSize * heightMapColSize, sizeof(int));
int *ignored = calloc(heightMapRowSize * heightMapColSize, sizeof(int));
//assert(visited && ignored);
​
DUMP(0, 0, 0, heightMap, heightMapRowSize, heightMapColSize);
total = 0;

k = 1;
for (i = 1; i  <  heightMapRowSize - 1; i ++) {
j = 1;
while (j  <  heightMapColSize - 1) {
x = i; y = j;
do {
m = heightMap[x][y];
w = fill(ignored, visited, k, heightMap, heightMapRowSize, heightMapColSize, x, y, &m, &x, &y);
if (w >= 0) {
if (w == 0) {
w = 1;
}
heightMap[x][y] += w;
total += w;
DUMP(x, y, w, heightMap, heightMapRowSize, heightMapColSize);
}
k ++;
} while (w != -1);
j ++;
}
}

free(visited);

}
#else
#define IDX(X, Y) ((X) * colsz + (Y))
const int offset[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int get_weight(int *visited, int *buff, int **map, int x, int y, int rowsz, int colsz) {
int i, j, k;
int w;
int base = -1;
​
memset(visited,  0, rowsz * colsz * sizeof(int));
memset(buff,    -1, rowsz * colsz * sizeof(int));

while (x != 0 && x != rowsz - 1 &&
y != 0 && y != colsz - 1) {

visited[IDX(x, y)] = 1;
​
for (k = 0; k  <  4; k ++) {
i = x + offset[k][0];
j = y + offset[k][1];
if (visited[IDX(i, j)]) continue;
w = map[i][j];
if (w  <  base) w = base; // propagate highest bar along the path
buff[IDX(i, j)] = w;
}

// locate lowest bar in surrounding and rebase to the lowest
base = -1;
for (i = 0; i  <  rowsz; i ++) {
for (j = 0; j  <  colsz; j ++) {
w = buff[IDX(i, j)];
if (w == -1 || visited[IDX(i, j)]) continue;
if (base == -1 || base > w) {
base = w;  // lowest bar in surrounding so far
x = i;
y = j;
}
}
}
}

return base;
}
typedef struct surr_s {
int x;
int y;
int h;
struct surr_s *left;
struct surr_s *right;
struct surr_s *dup;
} surr_t;
int cmp(const void *a, const void *b) {
return (*(surr_t *)b).h - (*(surr_t *)a).h;
}
int get_weight2(int *visited, surr_t *surr, int **map, int x, int y, int rowsz, int colsz) {
int low = -1, last = 0, this;
int i, j, k;
int w, base = 0;
​
memset(visited,  0, rowsz * colsz * sizeof(int));

while (x != 0 && x != rowsz - 1 &&
y != 0 && y != colsz - 1) {

visited[IDX(x, y)] |= 0x1;

for (k = 0; k  <  4; k ++) {
i = x + offset[k][0];
j = y + offset[k][1];
if (visited[IDX(i, j)]) continue;
visited[IDX(i, j)] |= 0x2;
w = map[i][j];
if (w  <  base) w = base; // propagate highest bar along the path
if (low != -1) {
this = low;
low = -1;
} else {
this = last ++;
}
surr[this].x = i;
surr[this].y = j;
surr[this].h = w;
}

base = -1;
for (i = 0; i  <  last; i ++) {
if (visited[IDX(surr[i].x, surr[i].y)] & 0x1) continue;
w = surr[i].h;
if (base == -1 || base > w) {
base = w;  // lowest bar in surrounding so far
x = surr[i].x;
y = surr[i].y;
low = i;
}
}
/*qsort(surr, last, sizeof(surr[0]), cmp);  // TLE 2!!!
low = last - 1;
if (surr[low].x == x &&
surr[low].y == y) {
low --; last --;
}
x = surr[low].x;
y = surr[low].y;
base = surr[low].h;*/
}

return base;
}
void insert(surr_t **pp, surr_t *node) {
surr_t *p = *pp;
if (!p) *pp = node;
else if (p->h == node->h) { node->dup = p->dup; p->dup = node; }
else if (p->h >  node->h) insert(&p->left, node);
else                      insert(&p->right, node);
}
int get_weight3(int *visited, surr_t *surr, int **map, int x, int y, int rowsz, int colsz) {
int i, j, k;
int w, base = 0;
surr_t *parent, *p, *node, *root = NULL;

memset(visited,  0, rowsz * colsz * sizeof(int));

while (x != 0 && x != rowsz - 1 &&
y != 0 && y != colsz - 1) {

visited[IDX(x, y)] |= 0x1;

for (k = 0; k  <  4; k ++) {
i = x + offset[k][0];
j = y + offset[k][1];
if (visited[IDX(i, j)]) continue;
visited[IDX(i, j)] |= 0x2;
w = map[i][j];
if (w  <  base) w = base; // propagate highest bar along the path
node = &surr[IDX(i, j)];
node->x = i;
node->y = j;
node->h = w;
node->left = node->right = node->dup = NULL;
insert(&root, node);        // still TLE!!! OMG
}
parent = NULL;
node = root;
while (node->left) {
parent = node;
node = node->left; // lowest bar in surrounding so far
}
if (node->dup) { // take node out of the tree
p = node->dup;
node->dup = p->dup;
node = p;
} else if (!parent) {
root = node->right;
} else {
parent->left = node->right;
}
x = node->x;
y = node->y;
base = node->h;  // the lowest one in the surrounding
}

return base;
}
int trapRainWater(int** heightMap, int heightMapRowSize, int heightMapColSize) {
int x, y;
int *visited, *weight, *buff;
int rowsz = heightMapRowSize;
int colsz = heightMapColSize;
int w, water = 0;

surr_t *root, *link, *surr;

visited = malloc(rowsz * colsz * sizeof(int));
weight = malloc(rowsz * colsz * sizeof(int));
buff = malloc(rowsz * colsz * sizeof(int));
surr = malloc(rowsz * colsz * sizeof(surr[0]));
//assert(visited && weight && buff && surr);

memset(weight, -1, rowsz * colsz * sizeof(int));
​
for (x = 1; x  <  rowsz - 1; x ++) {
for (y = 1; y  <  colsz - 1; y ++) {
//w = get_weight(visited, buff, heightMap, x, y, rowsz, colsz);
//w = get_weight2(visited, surr, heightMap, x, y, rowsz, colsz);
w = get_weight3(visited, surr, heightMap, x, y, rowsz, colsz);
//printf("[%d, %d]: %d\n", x, y, w);
if (w > heightMap[x][y]) {
water += w - heightMap[x][y];
}
}
}
free(visited);
free(weight);
free(buff);
free(surr);

return water;
}
#endif
``````
Copy The Code &

Input

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

Output

cmd
4

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int trap(int[] height) {
int leftIdx = 0;
int rightIdx = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int result = 0;
while (leftIdx  <  rightIdx) {
if (height[leftIdx] < height[rightIdx]) {
if (height[leftIdx] >= leftMax) {
leftMax = height[leftIdx];
} else {
result += leftMax - height[leftIdx];
}
leftIdx++;
} else {
if (height[rightIdx] >= rightMax) {
rightMax = height[rightIdx];
} else {
result += rightMax - height[rightIdx];
}
rightIdx--;
}
}
return result;
}
}
``````
Copy The Code &

Input

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

Output

cmd
4

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const trapRainWater = function (heightMap) {
const pq = new PriorityQueue((a, b) => a[2] < b[2])
const m = heightMap.length, n = heightMap[0].length

const visited = Array.from({ length: m }, () => Array(n).fill(false))

for(let i = 0; i  <  m; i++) {
visited[i][0] = visited[i][n - 1] = true
pq.push([i, 0, heightMap[i][0]])
pq.push([i, n - 1, heightMap[i][n - 1]])
}
for(let j = 1; j  <  n - 1; j++) {
visited[0][j] = visited[m - 1][j] = true
pq.push([0, j, heightMap[0][j]], [m - 1, j, heightMap[m - 1][j]])
}

let res = 0
const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
while(!pq.isEmpty()) {
const cur = pq.pop()
const [r, c, h] = cur
for(let dir of dirs) {
const newR = r + dir[0], newC = c + dir[1]
if(newR < 0 || newR >= m || newC < 0 || newC >= n || visited[newR][newC]) continue
visited[newR][newC] = true
res += Math.max(0, h - heightMap[newR][newC])
pq.push([newR, newC, Math.max(h, heightMap[newR][newC])])
}
}

return res

}
class PriorityQueue {
constructor(comparator = (a, b) => a > b) {
this.heap = []
this.top = 0
this.comparator = comparator
}
size() {
return this.heap.length
}
isEmpty() {
return this.size() === 0
}
peek() {
return this.heap[this.top]
}
push(...values) {
values.forEach((value) => {
this.heap.push(value)
this.siftUp()
})
return this.size()
}
pop() {
const poppedValue = this.peek()
const bottom = this.size() - 1
if (bottom > this.top) {
this.swap(this.top, bottom)
}
this.heap.pop()
this.siftDown()
return poppedValue
}
replace(value) {
const replacedValue = this.peek()
this.heap[this.top] = value
this.siftDown()
return replacedValue
}

parent = (i) => ((i + 1) >>> 1) - 1
left = (i) => (i << 1) + 1
right = (i) => (i + 1) << 1
greater = (i, j) => this.comparator(this.heap[i], this.heap[j])
swap = (i, j) => ([this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]])
siftUp = () => {
let node = this.size() - 1
while (node > this.top && this.greater(node, this.parent(node))) {
this.swap(node, this.parent(node))
node = this.parent(node)
}
}
siftDown = () => {
let node = this.top
while (
(this.left(node) < this.size() && this.greater(this.left(node), node)) ||
(this.right(node) < this.size() && this.greater(this.right(node), node))
) {
let maxChild =
this.right(node) < this.size() &&
this.greater(this.right(node), this.left(node))
? this.right(node)
: this.left(node)
this.swap(node, maxChild)
node = maxChild
}
}
}
``````
Copy The Code &

Input

cmd
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

cmd
10

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def trapRainWater(self, heightMap):
m, n, heap, trapped = len(heightMap), len(heightMap and heightMap[0]), [], 0
for i in range(m):
for j in range(n):
if i in {0, m - 1} or j in {0, n - 1}:
heapq.heappush(heap, (heightMap[i][j], i, j))
heightMap[i][j] = -1
while heap:
h, i, j = heapq.heappop(heap)
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 < x < m - 1 and 0 < y < n - 1 and heightMap[x][y] != -1:
trapped += max(h - heightMap[x][y], 0)
heapq.heappush(heap, (max(heightMap[x][y], h), x, y))
heightMap[x][y] = -1
return trapped
``````
Copy The Code &

Input

cmd
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

cmd
10