How hard is LeetCode 407. Trapping Rain Water II?

LeetCode 407. Trapping Rain Water II is rated Hard on LeetCode.

What is the time complexity of LeetCode 407. Trapping Rain Water II?

The Python solution on this page runs in O(m \times n \times \log (m \times n)).

What is the space complexity of LeetCode 407. Trapping Rain Water II?

The Python solution on this page uses O(m \times n), where m and n are the number of rows and columns in the matrix, respectively auxiliary space.

What topics does LeetCode 407. Trapping Rain Water II cover?

LeetCode 407. Trapping Rain Water II is tagged Breadth-First Search, Array, Matrix and Heap (Priority Queue) on LeetCode.

Trapping Rain Water II — LeetCode 407 Python Solution

HardBreadth-First SearchArrayMatrixHeap (Priority Queue)

Problem: #407
Pattern: Heap / Priority Queue
Reading time: 4 min
Source: leetcode.com

The problem

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

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.

Python solution

Python

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        vis = [[False] * n for _ in range(m)]
        pq = []
        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(pq, (heightMap[i][j], i, j))
                    vis[i][j] = True
        ans = 0
        dirs = (-1, 0, 1, 0, -1)
        while pq:
            h, i, j = heappop(pq)
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if x >= 0 and x < m and y >= 0 and y < n and not vis[x][y]:
                    ans += max(0, h - heightMap[x][y])
                    vis[x][y] = True
                    heappush(pq, (max(h, heightMap[x][y]), x, y))
        return ans

Complexity

Measure	Complexity
Time	O(m \times n \times \log (m \times n))
Space	O(m \times n), where m and n are the number of rows and columns in the matrix, respectively auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 407. Trapping Rain Water II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 407. Trapping Rain Water II?: LeetCode 407. Trapping Rain Water II is rated Hard on LeetCode.
What is the time complexity of LeetCode 407. Trapping Rain Water II?: The Python solution on this page runs in O(m \times n \times \log (m \times n)).
What is the space complexity of LeetCode 407. Trapping Rain Water II?: The Python solution on this page uses O(m \times n), where m and n are the number of rows and columns in the matrix, respectively auxiliary space.
What topics does LeetCode 407. Trapping Rain Water II cover?: LeetCode 407. Trapping Rain Water II is tagged Breadth-First Search, Array, Matrix and Heap (Priority Queue) on LeetCode.