# Solution For Trapping Rain Water Ii

Problem:

Given an array of integers representing heights of blocks where the width of each block is 1, compute how much water can be trapped after raining.

Example:

Input: [4,2,0,3,2,5] Output: 9

Explanation: In this example, the heights of the blocks are [4,2,0,3,2,5]. If it rains, 9 units of water (marked in blue) can be trapped.

Solution:

To solve this problem, we can use a stack to keep track of the indices of the blocks that form a valley. We start off by iterating through the entire array and for each block, we check if it is higher than the last block in the stack. If it is, we pop the stack until we find a block that is higher than the current block or the stack is empty. For each popped block, we calculate the amount of water that can be trapped between it and the current block and add it to our total. Finally, we push the current block index onto the stack.

Here is the implementation of the above algorithm:

“`python
def trap(height):
stack = [] trapped_water = 0

``````for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
bottom_index = stack.pop()
if not stack:
break
width = i - stack[-1] - 1
depth = min(height[i], height[stack[-1]]) - height[bottom_index]
trapped_water += width * depth
stack.append(i)

return trapped_water
``````

“`

Let’s break it down into steps:

1. We initialize an empty stack and a variable to keep track of the trapped water.
2. We iterate through the entire array using a for loop.
3. For each block, we check if it is higher than the last block in the stack. If it is, we pop the stack until we find a block that is higher than the current block or the stack is empty.
4. For each popped block, we calculate the amount of water that can be trapped between it and the current block and add it to our total.
5. Finally, we push the current block index onto the stack.
6. We return the total amount of trapped water.

This algorithm has a time complexity of O(n) and a space complexity of O(n), where n is the length of the input array.

Overall, this problem is a good application of stack data structure and can be solved easily using it.

## Step by Step Implementation For Trapping Rain Water Ii

```class Solution {
public int trapRainWater(int[][] heightMap) {
if(heightMap == null || heightMap.length == 0 || heightMap.length == 0)
return 0;

//PriorityQueue is a min heap with the first element being the minimum value
PriorityQueue queue = new PriorityQueue<>((a, b) -> a.height - b.height);
int nr = heightMap.length;
int nc = heightMap.length;
boolean[][] visited = new boolean[nr][nc];

//Add all the Cells on the border of the heightMap to the PriorityQueue
for(int r = 0; r < nr; r++) {
for(int c = 0; c < nc; c++) {
if(r == 0 || r == nr - 1 || c == 0 || c == nc - 1) {
queue.offer(new Cell(r, c, heightMap[r][c]));
visited[r][c] = true;
}
}
}

//Directions array for convenience
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int res = 0;

//While the PriorityQueue is not empty
while(!queue.isEmpty()) {
//Remove the minimum value cell from the PriorityQueue
Cell cell = queue.poll();

//For each direction
for(int[] dir : dirs) {
int row = cell.row + dir;
int col = cell.col + dir;

//If the next cell in that direction is valid and has not been visited
if(row >= 0 && row < nr && col >= 0 && col < nc && !visited[row][col]) {
//If the next cell's height is less than the current cell's height
if(heightMap[row][col] < cell.height) {
//The difference between the heights is the amount of water that can be stored in that cell
res += cell.height - heightMap[row][col];
}
//Add the next cell to the PriorityQueue with its height as the key
queue.offer(new Cell(row, col, Math.max(heightMap[row][col], cell.height)));
//Mark the next cell as visited
visited[row][col] = true;
}
}
}
return res;
}
}

//Cell class for convenience
class Cell {
int row;
int col;
int height;
public Cell(int row, int col, int height) {
this.row = row;
this.col = col;
this.height = height;
}
}```
```class Solution:
def trapRainWater(self, heightMap):
"""
:type heightMap: List[List[int]]
:rtype: int
"""
# base case
if not heightMap or not heightMap:
return 0

# get dimensions of heightMap
m = len(heightMap)
n = len(heightMap)

# initialize visited 2D array and heap
visited = [[False]*n for _ in range(m)]
heap = []

# add all boundary cells to the heap
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))
visited[i][j] = True

# initialize output
water = 0

# loop until heap is empty
while heap:
# get cell with minimum height from the heap
cell = heapq.heappop(heap)
i, j = cell, cell

# check surrounding cells
for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
# if cell is valid, not visited and its height is less than current cell's height
if 0 <= x < m and 0 <= y < n and not visited[x][y] and heightMap[x][y] < heightMap[i][j]:
# add difference in heights to output
water += heightMap[i][j] - heightMap[x][y]
# update height of adjacent cell with the current cell's height and mark it as visited
heightMap[x][y] = heightMap[i][j]
visited[x][y] = True
heapq.heappush(heap, (heightMap[x][y], x, y))

return water```
```var trapRainWater = function(heightMap) {
};```
```class Solution {
public:
int trapRainWater(vector>& heightMap) {
int m = heightMap.size();
int n = heightMap.size();
priority_queue, vector>, greater>> pq;
vector> visited(m, vector(n, false));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
pq.push(make_pair(heightMap[i][j], i * n + j));
visited[i][j] = true;
}
}
}
int res = 0;
vector dirs{0, -1, 0, 1, 0};
while (!pq.empty()) {
auto t = pq.top();
pq.pop();
int h = t.first, r = t.second / n, c = t.second % n;
for (int i = 0; i < 4; ++i) {
int nr = r + dirs[i], nc = c + dirs[i + 1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) continue;
res += max(0, h - heightMap[nr][nc]);
pq.push(make_pair(max(h, heightMap[nr][nc]), nr * n + nc));
visited[nr][nc] = true;
}
}
return res;
}
};```
```using System;

public class Solution {
public int TrapRainWater(int[,] heightMap) {
// check edge cases
if (heightMap == null || heightMap.GetLength(0) == 0 || heightMap.GetLength(1) == 0) {
return 0;
}

// initialize variables
int n = heightMap.GetLength(0);
int m = heightMap.GetLength(1);
int[,] dirs = new int[4,2] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int[,] visited = new int[n,m];
Queue queue = new Queue();
int res = 0;

// add all boundary cells to the queue
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
queue.Enqueue(new int[] {i, j});
visited[i, j] = 1;
}
}
}

// bfs
while (queue.Count != 0) {
int[] cell = queue.Dequeue();
int row = cell;
int col = cell;

// check all neighbors
for (int i = 0; i < 4; i++) {
int newRow = row + dirs[i,0];
int newCol = col + dirs[i,1];

// if new cell is valid and hasn't been visited yet
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && visited[newRow, newCol] == 0) {
// if new cell's height is less than current cell's height, add water
if (heightMap[newRow, newCol] < heightMap[row, col]) {
res += heightMap[row, col] - heightMap[newRow, newCol];
}

// update new cell's height to be the max of the current cell's height and the new cell's height
heightMap[newRow, newCol] = Math.Max(heightMap[row, col], heightMap[newRow, newCol]);

// add new cell to queue and mark as visited
queue.Enqueue(new int[] {newRow, newCol});
visited[newRow, newCol] = 1;
}
}
}

return res;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]