C# Solution for Trapping Rain Water II Problem
IntuitionThe problem is a 2D extension of the “trapping rainwater” problem. The key idea is that the amount of water trapped in a cell depends on the minimum bo
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem is a 2D extension of the “trapping rainwater” problem. The key idea is that the amount of water trapped in a cell depends on the minimum boundary height surrounding it. By processing cells starting from the lowest boundary, we can incrementally compute the trapped water while dynamically updating the boundary heights.

# Approach
<!-- Describe your approach to solving the problem. -->
1.	Boundary Initialization:
	•	Treat the boundary cells of the height map as initial barriers. These cells cannot trap any water since they lie on the edge.
	•	Add all boundary cells to a min-heap (priority queue) and mark them as visited. The heap ensures cells are processed in ascending order of height.
2.	Process Cells from the Min-Heap:
	•	Pop the smallest height cell from the heap.
	•	For each of its unvisited neighbors:
	•	Calculate the water trapped above the neighbor:
    water} = max(0, currentBoundaryHeight - neighborHeight)

	•	Update the neighbor’s effective boundary height to the larger of its own height or the current boundary height (Math.Max(currentBoundaryHeight, neighborHeight)).
	•	Add the neighbor to the heap and mark it as visited.
3.	Repeat Until All Cells Are Processed:
	•	Continue processing cells in increasing height order, ensuring the boundary heights dynamically expand to enclose trapped water.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
1.	Heap Operations:
	•	The priority queue holds O(m x n) cells in total.
	•	Each cell is added to the heap once and removed once.
	•	Insertion and removal in the heap take O(log(m x n)).
2.	Neighbor Traversal:
	•	Each cell has up to 4 neighbors, resulting in O(4 x m x n) = O(m x n).

Thus, the overall time complexity is: O(m x n log(m x n))

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
1.	Heap Storage:
	•	The min-heap can store up to O(m x n) cells.
2.	Visited Array:
	•	A m x n boolean array is used to track visited cells.
3.	Auxiliary Variables:
	•	Constant space is used for variables like directions and individual cell properties.

Total space complexity: O(m x n)

# Code
```csharp []
public class Solution {
    private class Cell {
        public int Row { get; }
        public int Col { get; }
        public int Height { get; }

        public Cell(int row, int col, int height) {
            Row = row;
            Col = col;
            Height = height;
        }
    }
    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;

        bool[,] visited = new bool[m, n];
        
        PriorityQueue<Cell, int> minHeap = new PriorityQueue<Cell, int>();

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

        int[] directions = { -1, 0, 1, 0, -1 }; 
        int waterTrapped = 0;
        while (minHeap.Count > 0) {
            Cell cell = minHeap.Dequeue();

            for (int k = 0; k < 4; k++) {
                int row = cell.Row + directions[k];
                int col = cell.Col + directions[k + 1];

                if (row >= 0 && row < m && col >= 0 && col < n && !visited[row, col]) {
                    visited[row, col] = true;

                    waterTrapped += Math.Max(0, cell.Height - heightMap[row][col]);

                    int updatedHeight = Math.Max(cell.Height, heightMap[row][col]);
                    minHeap.Enqueue(new Cell(row, col, updatedHeight), updatedHeight);
                }
            }
        }

        return waterTrapped;
    }
}
```
['C#']