aboutsummaryrefslogtreecommitdiff
path: root/trapping_rain_water2.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-18 21:04:01 -0700
committerJack Sangdahl <[email protected]>2025-01-18 21:04:01 -0700
commit9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a (patch)
tree366af9fa4501d75b5896b6c614b99a697362367d /trapping_rain_water2.c
parent3a737ea8dc8304354f75257b3f796e507354ccdc (diff)
downloadleetcode-9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a.tar.gz
leetcode-9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a.zip
407. trapping rain water 2
Diffstat (limited to 'trapping_rain_water2.c')
-rw-r--r--trapping_rain_water2.c95
1 files changed, 95 insertions, 0 deletions
diff --git a/trapping_rain_water2.c b/trapping_rain_water2.c
new file mode 100644
index 0000000..adde260
--- /dev/null
+++ b/trapping_rain_water2.c
@@ -0,0 +1,95 @@
+// 407. Trapping Rain Water II
+#include "leetcode.h"
+
+/*
+ * given an 'm x n' integer matrix 'heightMap' representing the height of each
+ * unit cell in a 2d elevation map, return the volume of water it can trap after
+ * raining
+ */
+
+struct cell {
+ int x;
+ int y;
+ int h;
+};
+
+struct heap {
+ struct cell *cells;
+ int size;
+};
+
+struct heap *heap_create(int capacity) {
+ struct heap *heap = (struct heap *)malloc(sizeof(struct heap));
+ heap->cells = (struct cell *)malloc(capacity * sizeof(struct cell));
+ heap->size = 0;
+ return heap;
+}
+
+void heap_push(struct heap *heap, int x, int y, int h) {
+ int i = heap->size++;
+ while (i && h < heap->cells[(i - 1) / 2].h)
+ heap->cells[i] = heap->cells[(i - 1) / 2], i = (i - 1) / 2;
+ heap->cells[i] = (struct cell){x, y, h};
+}
+
+struct cell heap_pop(struct heap *heap) {
+ struct cell root = heap->cells[0], prev = heap->cells[--heap->size];
+ int i, child;
+ for (i = 0; (child = 2 * i + 1) < heap->size; i = child) {
+ if (child + 1 < heap->size &&
+ heap->cells[child].h > heap->cells[child + 1].h)
+ child++;
+ if (prev.h <= heap->cells[child].h)
+ break;
+ heap->cells[i] = heap->cells[child];
+ }
+ return heap->cells[i] = prev, root;
+}
+
+int trapRainWater(int **heightMap, int heightMapSize, int *heightMapColSize) {
+ int m = heightMapSize, n = *heightMapColSize, water = 0, max_height = 0;
+ bool vis[m][n];
+ if (m < 3 || n < 3)
+ return 0;
+ memset(vis, false, sizeof(vis));
+ struct heap *heap = heap_create(m * n);
+ for (int i = 0; i < m; i++)
+ for (int j = 0; j < n; j++)
+ if (!i || i == m - 1 || !j || j == n - 1) {
+ heap_push(heap, i, j, heightMap[i][j]);
+ vis[i][j] = true;
+ }
+ int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
+ while (heap->size) {
+ struct cell cell = heap_pop(heap);
+ max_height = cell.h > max_height ? cell.h : max_height;
+ for (int i = 0; i < 4; i++) {
+ int x = cell.x + dir[i][0], y = cell.y + dir[i][1];
+ if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
+ vis[x][y] = true;
+ heightMap[x][y] < max_height ? (water += max_height - heightMap[x][y],
+ heap_push(heap, x, y, max_height))
+ : heap_push(heap, x, y, heightMap[x][y]);
+ }
+ }
+ }
+ free(heap->cells);
+ free(heap);
+ return water;
+}
+
+int main() {
+ int hm1i[3][6] = {{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}};
+ int hm2i[5][6] = {{3, 3, 3, 3, 3},
+ {3, 2, 2, 2, 3},
+ {3, 2, 1, 2, 3},
+ {3, 2, 2, 2, 3},
+ {3, 3, 3, 3, 3}};
+ struct two_d_arr hm1, hm2, hm3;
+ two_d_arr_init(&hm1, ARRAY_SIZE(hm1i), ARRAY_SIZE(hm1i[0]), hm1i);
+ two_d_arr_init(&hm2, ARRAY_SIZE(hm2i), ARRAY_SIZE(hm2i[0]), hm2i);
+ printf("%d\n",
+ trapRainWater(hm1.arr, hm1.row_size, hm1.col_size)); // expect: 4
+ printf("%d\n",
+ trapRainWater(hm2.arr, hm2.row_size, hm2.col_size)); // expect: 10
+}