aboutsummaryrefslogtreecommitdiff
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
parent3a737ea8dc8304354f75257b3f796e507354ccdc (diff)
downloadleetcode-9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a.tar.gz
leetcode-9a3751a7bebaf2a138a3ec91cd38afc27dc54f6a.zip
407. trapping rain water 2
-rw-r--r--trapping_rain_water2.c95
-rw-r--r--trapping_rain_water2.py56
2 files changed, 151 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
+}
diff --git a/trapping_rain_water2.py b/trapping_rain_water2.py
new file mode 100644
index 0000000..594b7c5
--- /dev/null
+++ b/trapping_rain_water2.py
@@ -0,0 +1,56 @@
+# 407. Trapping Rain Water II
+import heapq
+
+"""
+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
+"""
+
+
+class Solution(object):
+ def trapRainWater(self, heightMap):
+ """
+ :type heightMap: List[List[int]]
+ :rtype: int
+ """
+ m, n = len(heightMap), len(heightMap[0])
+ if m < 3 or n < 3:
+ return 0
+ heap = []
+ 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))
+ heightMap[i][j] = -1
+ level, ans = 0, 0
+ while heap:
+ h, x, y = heapq.heappop(heap)
+ level = max(h, level)
+ for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
+ if 0 <= i < m and 0 <= j < n and heightMap[i][j] != -1:
+ heapq.heappush(heap, (heightMap[i][j], i, j))
+ if heightMap[i][j] < level:
+ ans += level - heightMap[i][j]
+ heightMap[i][j] = -1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.trapRainWater(
+ heightMap=[[1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1]]
+ )
+ )
+ print(
+ obj.trapRainWater(
+ heightMap=[
+ [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],
+ ]
+ )
+ )