Min heap (with explanation)
Approach

Ccheck if the heightMap is empty or if the first row is empty. If either condition is true, it returns 0 because no water can be trapped.


Calculate
# Approach
1. Ccheck if the heightMap is empty or if the first row is empty. If either condition is true, it returns 0 because no water can be trapped.

2. Calculate the number of rows and columns in the heightMap.
- A visited matrix of the same dimensions as heightMap is initialized to keep track of which cells have been processed.
- A min-heap is initialized to store the boundary cells of the heightMap. The heap stores tuples of the form (height, row, column).
Boundary Cells:

3. All boundary cells (cells in the first and last rows, and cells in the first and last columns) are pushed into the heap and marked as visited. 
- This is because water can only be trapped inside the boundary, and the boundary cells determine the water level.
Processing Cells:

4. The algorithm processes cells in the heap starting from the cell with the smallest height. 
- This ensures that we always consider the lowest boundary first.

5. For each cell, it checks its four neighbors (up, down, left, right).
- If a neighbor is within bounds and has not been visited, it calculates the water that can be trapped at that neighbor. The water trapped is the difference between the current cell's height and the neighbor's height, if the neighbor's height is lower.
- The trapped water is added to the trapped_water variable.
- The neighbor's height is updated to the current cell's height (or the water level) to prevent further water from being trapped at that level.
- The neighbor is marked as visited and pushed into the heap.

6. After processing all cells, the total amount of trapped water is returned.


# Complexity
- Time complexity:
$$O(m * n * log(m * n))$$
-- Initializing the visited matrix: O(m * n).
-- Pushing boundary cells into the heap:
Two loops for the first and last columns: O(m) each
Two loops for the first and last rows: O(n) each
Total for pushing boundary cells: O(m + n)
Each push operation into the heap takes O(log(m * n)) time in the worst case.
-- The while loop runs until the heap is empty. In the worst case, each cell is pushed into the heap once and popped once.
Each pop operation from the heap takes O(log(m * n)) time.
For each cell, there are up to 4 neighbors to check, and each push operation into the heap takes O(log(m * n)) time.

- Space complexity:
$$O(m * n)$$
-- The visited matrix is of size m * n.
-- The heap can contain up to m * n elements in the worst case (if all cells are pushed into the heap).

# Code
```python3 []
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        # Check if the elevation map is empty
        if not heightMap or not heightMap[0]:
            return 0

        # Get the dimensions of the elevation map
        rows, cols = len(heightMap), len(heightMap[0])

        # Initialize a visited matrix to keep track of visited cells
        visited = [[False] * cols for _ in range(rows)]

        # Initialize a min-heap to process cells starting from the boundary
        heap = []

        # Push all boundary cells into the heap and mark them as visited
        for i in range(rows):
            for j in [0, cols - 1]:
                visited[i][j] = True
                heapq.heappush(heap, (heightMap[i][j], i, j))

        for i in [0, rows - 1]:
            for j in range(1, cols - 1):
                visited[i][j] = True
                heapq.heappush(heap, (heightMap[i][j], i, j))

        # Initialize the result to store the total trapped water
        trapped_water = 0

        # Process cells from the heap
        while heap:
            # Pop the cell with the smallest height from the heap
            current_height, x, y = heapq.heappop(heap)

            # Check all four possible directions (up, down, left, right)
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                new_x, new_y = x + dx, y + dy

                # Check if the new cell is within bounds and not visited
                if 0 <= new_x < rows and 0 <= new_y < cols and not visited[new_x][new_y]:
                    # Calculate the water that can be trapped at the new cell
                    if heightMap[new_x][new_y] < current_height:
                        trapped_water += current_height - heightMap[new_x][new_y]
                        # Update the height to the current height
                        heightMap[new_x][new_y] = current_height

                    # Mark the new cell as visited and push it into the heap
                    visited[new_x][new_y] = True
                    heapq.heappush(heap, (heightMap[new_x][new_y], new_x, new_y))

        return trapped_water
```
``` javascript []
/**
 * @param {number[][]} heightMap
 * @return {number}
 */
var trapRainWater = function(heightMap) {
    // Check if the elevation map is empty
    if (!heightMap || heightMap.length === 0 || heightMap[0].length === 0) {
        return 0;
    }

    // Get the dimensions of the elevation map
    const rows = heightMap.length;
    const cols = heightMap[0].length;

    // Initialize a visited matrix to keep track of visited cells
    const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

    // Initialize a min-heap to process cells starting from the boundary
    const heap = new MinPriorityQueue({ priority: x => x[0] });

    // Push all boundary cells into the heap and mark them as visited
    for (let i = 0; i < rows; i++) {
        for (let j of [0, cols - 1]) {
            visited[i][j] = true;
            heap.enqueue([heightMap[i][j], i, j]);
        }
    }

    for (let i of [0, rows - 1]) {
        for (let j = 1; j < cols - 1; j++) {
            visited[i][j] = true;
            heap.enqueue([heightMap[i][j], i, j]);
        }
    }

    // Initialize the result to store the total trapped water
    let trappedWater = 0;

    // Process cells from the heap
    while (!heap.isEmpty()) {
        // Pop the cell with the smallest height from the heap
        const [currentHeight, x, y] = heap.dequeue().element;

        // Check all four possible directions (up, down, left, right)
        for (let [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
            const newX = x + dx;
            const newY = y + dy;

            // Check if the new cell is within bounds and not visited
            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !visited[newX][newY]) {
                // Calculate the water that can be trapped at the new cell
                if (heightMap[newX][newY] < currentHeight) {
                    trappedWater += currentHeight - heightMap[newX][newY];
                    // Update the height to the current height
                    heightMap[newX][newY] = currentHeight;
                }

                // Mark the new cell as visited and push it into the heap
                visited[newX][newY] = true;
                heap.enqueue([heightMap[newX][newY], newX, newY]);
            }
        }
    }

    return trappedWater;
};
```
``` php []
class Solution {

    /**
     * @param Integer[][] $heightMap
     * @return Integer
     */
    function trapRainWater($heightMap) {
        // Check if the elevation map is empty
        if (empty($heightMap) || empty($heightMap[0])) {
            return 0;
        }

        // Get the dimensions of the elevation map
        $rows = count($heightMap);
        $cols = count($heightMap[0]);

        // Initialize a visited matrix to keep track of visited cells
        $visited = array_fill(0, $rows, array_fill(0, $cols, false));

        // Initialize a min-heap to process cells starting from the boundary
        $heap = new Cell();

        // Push all boundary cells into the heap and mark them as visited
        for ($i = 0; $i < $rows; $i++) {
            foreach ([0, $cols - 1] as $j) {
                $visited[$i][$j] = true;
                $heap->insert([$heightMap[$i][$j], $i, $j]);
            }
        }

        for ($j = 1; $j < $cols - 1; $j++) {
            foreach ([0, $rows - 1] as $i) {
                $visited[$i][$j] = true;
                $heap->insert([$heightMap[$i][$j], $i, $j]);
            }
        }

        // Initialize the result to store the total trapped water
        $trappedWater = 0;

        // Process cells from the heap
        while (!$heap->isEmpty()) {
            // Pop the cell with the smallest height from the heap
            list($currentHeight, $x, $y) = $heap->extract();

            // Check all four possible directions (up, down, left, right)
            foreach ([[1, 0], [-1, 0], [0, 1], [0, -1]] as list($dx, $dy)) {
                $newX = $x + $dx;
                $newY = $y + $dy;

                // Check if the new cell is within bounds and not visited
                if ($newX >= 0 && $newX < $rows && $newY >= 0 && $newY < $cols && !$visited[$newX][$newY]) {
                    // Calculate the water that can be trapped at the new cell
                    if ($heightMap[$newX][$newY] < $currentHeight) {
                        $trappedWater += $currentHeight - $heightMap[$newX][$newY];
                        // Update the height to the current height
                        $heightMap[$newX][$newY] = $currentHeight;
                    }

                    // Mark the new cell as visited and push it into the heap
                    $visited[$newX][$newY] = true;
                    $heap->insert([$heightMap[$newX][$newY], $newX, $newY]);
                }
            }
        }

        return $trappedWater;
    }
}


class Cell extends SplHeap {
    protected function compare($value1, $value2) {
        return $value2[0] - $value1[0];
    }
}
```
['PHP', 'Heap (Priority Queue)', 'Matrix', 'Python3', 'JavaScript']