Skip to content

407. Trapping Rain Water II

Array Breadth-First Search Heap (Priority Queue) Matrix

Problem - Trapping Rain Water II

Hard

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.

 

Example 1:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.

Example 2:

Input: 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]]
Output: 10

 

Constraints:

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200
  • 0 <= heightMap[i][j] <= 2 * 104

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        visited = [[False] * n for _ in range(m)]
        priority_queue = []

        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    heappush(priority_queue, (heightMap[i][j], i, j))
                    visited[i][j] = True

        directions = (-1, 0, 1, 0, -1)
        result = 0

        while priority_queue:
            height, i, j = heappop(priority_queue)
            for dir1, dir2 in pairwise(directions):
                x, y = i + dir1, j + dir2
                if x >= 0 and x < m and y >= 0 and y < n and not visited[x][y]:
                    result += max(0, height - heightMap[x][y])
                    heappush(priority_queue, (max(height, heightMap[x][y]), x, y))
                    visited[x][y] = True

        return result

Submission Stats:

  • Runtime: 132 ms (51.98%)
  • Memory: 20.5 MB (37.70%)