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[0].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[0].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[0];
                int col = cell.col + dir[1];
                
                //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[0]:
            return 0
        
        # get dimensions of heightMap
        m = len(heightMap)
        n = len(heightMap[0])
        
        # 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[1], cell[2]
            
            # 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
                    # add adjacent cell to the heap
                    heapq.heappush(heap, (heightMap[x][y], x, y))
        
        return water

var trapRainWater = function(heightMap) {
    // your code here
};

class Solution {
public:
    int trapRainWater(vector>& heightMap) {
        int m = heightMap.size();
        int n = heightMap[0].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[0];
            int col = cell[1];
            
            // 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;
    }
}