Trapping Rain Water Ii

                                            
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty()) return 0;
        
        const int m = heightMap.size();
        const int n = heightMap[0].size();
        
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> minHeap;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        for (int i = 0; i < m; ++i) {
            minHeap.emplace(heightMap[i][0], i, 0);
            minHeap.emplace(heightMap[i][n - 1], i, n - 1);
            visited[i][0] = visited[i][n - 1] = true;
        }
        
        for (int j = 1; j < n - 1; ++j) {
            minHeap.emplace(heightMap[0][j], 0, j);
            minHeap.emplace(heightMap[m - 1][j], m - 1, j);
            visited[0][j] = visited[m - 1][j] = true;
        }
        
        int water = 0;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        
        while (!minHeap.empty()) {
            auto [h, r, c] = minHeap.top();
            minHeap.pop();
            
            for (int k = 0; k < 4; ++k) {
                int nr = r + dirs[k];
                int nc = c + dirs[k + 1];
                
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
                    water += max(0, h - heightMap[nr][nc]);
                    minHeap.emplace(max(h, heightMap[nr][nc]), nr, nc);
                    visited[nr][nc] = true;
                }
            }
        }
        
        return water;
    }
};

                                            
import java.util.PriorityQueue;

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

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

        for (int i = 0; i < m; i++) {
            pq.offer(new int[]{i, 0, heightMap[i][0]});
            pq.offer(new int[]{i, n - 1, heightMap[i][n - 1]});
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }

        for (int j = 0; j < n; j++) {
            pq.offer(new int[]{0, j, heightMap[0][j]});
            pq.offer(new int[]{m - 1, j, heightMap[m - 1][j]});
            visited[0][j] = true;
            visited[m - 1][j] = true;
        }

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

            for (int[] dir : dirs) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    waterTrapped += Math.max(0, height - heightMap[newRow][newCol]);
                    pq.offer(new int[]{newRow, newCol, Math.max(height, heightMap[newRow][newCol])});
                }
            }
        }

        return waterTrapped;
    }
}

                                            
class Solution(object):
    def trapRainWater(self, heightMap):
        """
        :type heightMap: List[List[int]]
        :rtype: int
        """
        if not heightMap or not heightMap[0]:
            return 0
        
        import heapq
        m, n = len(heightMap), len(heightMap[0])
        visited = set()
        heap = []
        res = 0
        
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    heapq.heappush(heap, (heightMap[i][j], i, j))
                    visited.add((i, j))
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while heap:
            h, i, j = heapq.heappop(heap)
            for x, y in directions:
                ni, nj = i + x, j + y
                if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in visited:
                    nh = max(h, heightMap[ni][nj])
                    res += max(0, nh - heightMap[ni][nj])
                    heapq.heappush(heap, (nh, ni, nj))
                    visited.add((ni, nj))
        
        return res

                                            
class MinHeap<T> {
    heap: T[];
    compare: (a: T, b: T) => number;

    constructor(compare: (a: T, b: T) => number) {
        this.heap = [];
        this.compare = compare;
    }

    push(value: T) {
        this.heap.push(value);
        this.siftUp(this.heap.length - 1);
    }

    pop() {
        const rootValue = this.heap[0];
        const lastValue = this.heap.pop();
        if (this.heap.length > 0 && lastValue !== undefined) {
            this.heap[0] = lastValue;
            this.siftDown(0);
        }
        return rootValue;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    siftUp(index: number) {
        let parentIndex = Math.floor((index - 1) / 2);
        while (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
            parentIndex = Math.floor((index - 1) / 2);
        }
    }

    siftDown(index: number) {
        let leftChildIndex = 2 * index + 1;
        let rightChildIndex = 2 * index + 2;
        let smallestIndex = index;

        if (leftChildIndex < this.heap.length && this.compare(this.heap[leftChildIndex], this.heap[smallestIndex]) < 0) {
            smallestIndex = leftChildIndex;
        }
        if (rightChildIndex < this.heap.length && this.compare(this.heap[rightChildIndex], this.heap[smallestIndex]) < 0) {
            smallestIndex = rightChildIndex;
        }

        if (smallestIndex !== index) {
            [this.heap[index], this.heap[smallestIndex]] = [this.heap[smallestIndex], this.heap[index]];
            this.siftDown(smallestIndex);
        }
    }
}

function trapRainWater(heightMap: number[][]): number {
    if (heightMap.length === 0) return 0;

    const m = heightMap.length;
    const n = heightMap[0].length;
    let volume = 0;

    const heap = new MinHeap<number[]>((a, b) => heightMap[a[0]][a[1]] - heightMap[b[0]][b[1]]);
    const visited = Array.from({ length: m }, () => Array(n).fill(false));

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

    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    while (!heap.isEmpty()) {
        const [i, j] = heap.pop();
        for (const [dx, dy] of directions) {
            const x = i + dx;
            const y = j + dy;
            if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {
                volume += Math.max(0, heightMap[i][j] - heightMap[x][y]);
                heap.push([x, y]);
                visited[x][y] = true;
                heightMap[x][y] = Math.max(heightMap[x][y], heightMap[i][j]);
            }
        }
    }

    return volume;
};

                                            
class Solution {
    func trapRainWater(_ heightMap: [[Int]]) -> Int {
        // Check for edge cases
        if heightMap.isEmpty || heightMap[0].isEmpty {
            return 0
        }
        
        let m = heightMap.count
        let n = heightMap[0].count
        var visited = Array(repeating: Array(repeating: false, count: n), count: m)
        var minHeap: [(h: Int, r: Int, c: Int)] = []
        var result = 0
        
        // Add all boundary cells to the minHeap
        for i in 0..<m {
            visited[i][0] = true
            visited[i][n - 1] = true
            minHeap.append((h: heightMap[i][0], r: i, c: 0))
            minHeap.append((h: heightMap[i][n - 1], r: i, c: n - 1))
        }
        
        for j in 1..<(n - 1) {
            visited[0][j] = true
            visited[m - 1][j] = true
            minHeap.append((h: heightMap[0][j], r: 0, c: j))
            minHeap.append((h: heightMap[m - 1][j], r: m - 1, c: j))
        }
        
        minHeap.sort { $0.h < $1.h }
        
        // Define directions for visiting neighbors
        let directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while !minHeap.isEmpty {
            let curr = minHeap.removeFirst()
            for dir in directions {
                let newRow = curr.r + dir.0
                let newCol = curr.c + dir.1
                
                if newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol] {
                    visited[newRow][newCol] = true
                    result += max(0, curr.h - heightMap[newRow][newCol])
                    minHeap.append((h: max(curr.h, heightMap[newRow][newCol]), r: newRow, c: newCol))
                    minHeap.sort { $0.h < $1.h }
                }
            }
        }
        
        return result
    }
}

                                            
class Solution {
    fun trapRainWater(heightMap: Array<IntArray>): Int {
        if (heightMap.isEmpty() || heightMap[0].isEmpty()) {
            return 0
        }
        
        val m = heightMap.size
        val n = heightMap[0].size
        
        val visited = Array(m) { BooleanArray(n) }
        val pq = PriorityQueue<Cell> { a, b -> a.h - b.h }
        
        for (i in 0 until m) {
            visited[i][0] = true
            visited[i][n - 1] = true
            pq.offer(Cell(i, 0, heightMap[i][0]))
            pq.offer(Cell(i, n - 1, heightMap[i][n - 1]))
        }
        
        for (j in 1 until n - 1) {
            visited[0][j] = true
            visited[m - 1][j] = true
            pq.offer(Cell(0, j, heightMap[0][j]))
            pq.offer(Cell(m - 1, j, heightMap[m - 1][j]))
        }
        
        val dirs = arrayOf(0, 1, 0, -1, 0)
        var trapped = 0
        var maxHeight = Int.MIN_VALUE
        
        while (pq.isNotEmpty()) {
            val cell = pq.poll()
            maxHeight = maxOf(maxHeight, cell.h)
            for (d in 0 until 4) {
                val ni = cell.i + dirs[d]
                val nj = cell.j + dirs[d + 1]
                if (ni in 0 until m && nj in 0 until n && !visited[ni][nj]) {
                    visited[ni][nj] = true
                    trapped += maxOf(0, maxHeight - heightMap[ni][nj])
                    pq.offer(Cell(ni, nj, heightMap[ni][nj]))
                }
            }
        }
        
        return trapped
    }

    data class Cell(val i: Int, val j: Int, val h: Int)
}

To solve this coding challenge, we need to determine the volume of water that can be trapped by a given 2D elevation map after raining. The solution involves using a variant of Dijkstra’s algorithm with a min-heap to effectively simulate the trapping of water in the matrix.

Explanation

Here's a detailed step-by-step explanation of how the algorithm solves the problem:

Initialize Empty Structures :

We use a min-heap (priority queue) to track the cells by their height.
We also maintain a set to track visited cells, ensuring we don't process any cell more than once.

Boundary Initialization :

All the cells on the boundary of the matrix are pushed into the min-heap, and marked as visited. This is because the boundary cells cannot trap any water, but they set a boundary from which we will process the inner cells.

Process Cells in Min-Heap :

We repeatedly extract the cell with the minimum height from the heap.
For each extracted cell, we look at its 4 neighboring cells (top, bottom, left, and right).
If a neighboring cell has not been visited, we calculate the potential water trapped at this cell.
The trapped water at each neighbor depends on the difference between the height of the current cell and the neighbor. If the neighbor is lower, water can be trapped.
We update our result with the trapped water and push the neighbor cell into the heap, marking it as visited.

Continue :

We continue this process until all reachable cells (from the boundary inward) have been processed.

By the end of this process, the result will be the total volume of trapped water in the grid.

Detailed Steps in Pseudocode

Below is the pseudocode which follows the detailed steps:

Initialization :

                                            
# Import necessary modules
initialize a min-heap (priority queue)
initialize a set for visited cells
initialize a variable for the total volume of trapped water

# If heightMap is empty or the first row is empty, return 0
if heightMap is empty or heightMap[0] is empty:
return 0

Boundary Setup :

                                            
# Get dimensions of heightMap
m, n = number of rows in heightMap, number of columns in heightMap

# Push boundary cells into the heap and mark them as visited
for each row index i from 0 to m-1:
for each column index j from 0 to n-1:
if cell is on the boundary (i == 0 or i == m-1 or j == 0 or j == n-1):
push (heightMap[i][j], i, j) into min-heap
add (i, j) to visited set

Processing Cells :

                                            
# Define possible four directions (right, left, down, up)
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# While the heap is not empty:
while min-heap is not empty:
# Pop the cell with the minimum height
current_height, i, j = pop from min-heap

# Iterate through all four possible directions
for x, y in directions:
ni, nj = i + x, j + y

# If the neighboring cell is within bounds and not visited:
if ni is within bounds and nj is within bounds and (ni, nj) not in visited:
# Calculate the new height
neighbor_height = heightMap[ni][nj]
nh = maximum of (current_height, neighbor_height)

# Calculate trapped water
trapped_water = maximum of (0, nh - neighbor_height)

# Add trapped water to total volume
add trapped_water to total volume

# Push the neighbor cell into the heap with the updated height
push (nh, ni, nj) into min-heap

# Mark the neighbor cell as visited
add (ni, nj) to visited set

Return Result :

                                            
# Return the total volume of trapped water
return total volume

This methodology ensures that we effectively simulate water flow, filling up lower areas bounded by higher elevation cells, and compute the total volume of water trapped accurately.