A {C}rude Solution to Trapping Rain Water in 3D
Intuition\nThis is a 3D variation of the previous 2D problem. The biggest problem is figuring out how much water can be trapped in each cell. The key intuition 
# Intuition\nThis is a 3D variation of the previous 2D problem. The biggest problem is figuring out how much water can be trapped in each cell. The key intuition here would be that the amount of water trapped in a cell is determined by the lowest boundary around it. That\'s because water will fill up to the height of the lowest boundary before it starts to spill over.\n\n# Approach\n- We use the boundary cells of the matrix as starting points; water can\'t be trapped above the height of these otherwise it\'d just overflow.\n- Since C doesn\'t have a priority queue built-in like C++, we manually create a min-heap with all boundary cells. The heap is prioritized by the cell heights, so we always process the lowest cell first.\n- We\'ll use a 2D array to keep track of processed cells. Important because we don\'t want to reprocess the cells, they should be added to the heap only *once!*\n- Pop the cell with the lowest height from the heap.\n- Check its four neighbouring cells (up/down/left/right). For each neighbour, do:\n    - If the neighbour\'s height is less than the current cell\'s height, water *can* be trapped. The trapped water volume is the difference between the current cell\'s height and the neighbour\'s height.\n    - Update the neighbour\'s height to the maximum of its original height and the current cell\'s height (if the water is trapped). This essentially raises the ground level to the new water level.\n- Push the neighbour into the heap with its updated weight\n\nThen we just rinse and repeat until we\'re done with all the cells. The heap is very important, because we need to always process the cell with the next lowest boundary. Not necessary with C++ because it has a priority queue already.\n\n# Complexity\n- Time complexity:\n$$O((m*n) * log(m*n))$$\n\n- Space complexity:\n$$O(m*n)$$\n\n# Code\n```\n#include <stdlib.h>\n#include <string.h>\n\ntypedef struct { int x, y, h; } Cell;\ntypedef struct { Cell* cells; int size; } Heap;\n\nHeap* createHeap(int capacity) {\n    Heap* heap = malloc(sizeof(Heap));\n    heap->cells = malloc(capacity * sizeof(Cell));\n    return heap->size = 0, heap;\n}\n\nvoid push(Heap* heap, int x, int y, int h) {\n    int i = heap->size++;\n    while (i && h < heap->cells[(i - 1) / 2].h) heap->cells[i] = heap->cells[(i - 1) / 2], i = (i - 1) / 2;\n    heap->cells[i] = (Cell) {x, y, h};\n}\n\nCell pop(Heap* heap) {\n    Cell root = heap->cells[0], last = heap->cells[--heap->size];\n    int i, child;\n    for (i = 0; (child = 2 * i + 1) < heap->size; i = child) {\n        if (child + 1 < heap->size && heap->cells[child].h > heap->cells[child + 1].h) child++;\n        if (last.h <= heap->cells[child].h) break;\n        heap->cells[i] = heap->cells[child];\n    }\n    return heap->cells[i] = last, root;\n}\n\nint trapRainWater(int** heightMap, int heightMapSize, int* heightMapColSize){\n    int m = heightMapSize, n = *heightMapColSize, visited[m][n], water = 0, maxHeight = 0;\n    if (m < 3 || n < 3) return 0;\n    memset(visited, 0, sizeof(visited));\n    Heap* heap = createHeap(m * n);\n    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (i == 0 || i == m - 1 || j == 0 || j == n - 1) push(heap, i, j, heightMap[i][j]), visited[i][j] = 1;\n    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n    while (heap->size) {\n        Cell cell = pop(heap);\n        maxHeight = cell.h > maxHeight ? cell.h : maxHeight;\n        for (int i = 0; i < 4; i++) {\n            int x = cell.x + dirs[i][0], y = cell.y + dirs[i][1];\n            if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) visited[x][y] = 1, heightMap[x][y] < maxHeight ? (water += maxHeight - heightMap[x][y], push(heap, x, y, maxHeight)) : push(heap, x, y, heightMap[x][y]);\n        }\n    }\n    free(heap->cells), free(heap);\n    return water;\n}\n```
['C']