#407

Hard

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Trapping Rain Water II

Solve Trapping Rain Water II using breadth-first search and priority queues for efficient water trapping in a matrix.

array breadth first search heap priority queue matrix

Problem Statement

Given a matrix of integers, heightMap, where each cell represents the elevation of that cell in a 2D terrain, your task is to compute the total amount of rainwater trapped between the cells after it rains. The cells can hold water if there are lower elevation areas surrounded by higher elevation areas. You must return the total volume of water trapped.

This problem is solved using a breadth-first search (BFS) combined with a priority queue (heap) to simulate how water can flow and accumulate in the matrix. Start from the border cells and move inward, filling lower cells first and keeping track of the trapped water.

Examples

Example 1

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]

Output: 4

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

Example details omitted.

Constraints

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

Solution Approach

BFS with Priority Queue

We use a BFS approach with a priority queue (min-heap) to simulate the process of water flowing through the matrix. Starting from the matrix's border, the algorithm pushes all boundary cells into the heap and gradually processes each cell by checking the neighboring cells to determine the water trapped. By processing the smallest boundary heights first, we ensure that the water flows optimally, and no higher cells block the flow.

Simulation of Water Flow

For each cell, we check its neighbors. If the neighboring cell is lower in elevation, water can be trapped. The trapped water amount is calculated based on the height difference between the current cell and the neighboring cell. Once a cell is processed, the neighboring cells are added to the heap for further processing.

Efficient Time Complexity

The approach is efficient with a time complexity of O(m * n * log(m * n)), where m and n are the dimensions of the heightMap matrix. This is due to the operations on the priority queue, which take logarithmic time relative to the number of cells.

Complexity Analysis

Metric	Value
Time	O(m \cdot n \times \log{m \cdot n})
Space	O(m \times n)

The time complexity is O(m * n * log(m * n)) due to the use of a priority queue (min-heap) that processes each matrix cell. Each cell is pushed and popped from the heap exactly once, making the heap operations logarithmic with respect to the total number of cells. The space complexity is O(m * n) to store the matrix and the queue elements.

What Interviewers Usually Probe

The candidate demonstrates an understanding of how BFS and priority queues can be applied to 2D matrix problems.
The candidate identifies key edge cases and efficiently handles varying matrix sizes and elevations.
The candidate can explain the flow of water across different heights in a matrix and why boundary processing is crucial.

Common Pitfalls or Variants

Common pitfalls

Failing to use a priority queue effectively may lead to inefficient traversal and incorrect water trapping calculations.
Overcomplicating the problem with unnecessary space or time-consuming operations.
Not handling edge cases where the matrix is very small or where the matrix has constant elevation values, which could lead to incorrect results.

Follow-up variants

Implementing the solution without a priority queue, relying on a simpler flood-fill approach.
Optimizing space complexity by using in-place modifications to the heightMap matrix.
Handling varying matrix shapes (non-square matrices) and ensuring correctness in all cases.

FAQ

How can I optimize Trapping Rain Water II if the matrix size is very large?

For large matrices, ensure you use the priority queue efficiently to minimize unnecessary operations. Avoid naive flood-fill algorithms that don't utilize a heap for optimal processing.

Can I use a brute force solution to solve Trapping Rain Water II?

While brute force is possible, it is inefficient for large matrices. The BFS with priority queue approach offers a much faster solution with a better time complexity.

What is the main advantage of using BFS with a priority queue for this problem?

The main advantage is that it allows us to simulate the flow of water from the boundary inward, ensuring an optimal solution with minimal processing time, using logarithmic heap operations.

What is the time complexity of the optimal solution for Trapping Rain Water II?

The time complexity is O(m * n * log(m * n)), where m and n are the dimensions of the matrix. This is due to the priority queue operations, which take logarithmic time for each cell.

How do I handle edge cases in Trapping Rain Water II?

Edge cases include very small matrices or matrices where all cells have the same elevation. The algorithm handles these efficiently, but make sure to verify that your implementation works for these edge cases.

terminal

Solution

Solution 1: Priority Queue (Min Heap)

This is a variant of the trapping rain water problem. Since the heights on the matrix boundaries are fixed, we can add these boundary heights to a priority queue. Then, we repeatedly take out the minimum height from the priority queue and compare it with the heights of its four adjacent cells. If an adjacent cell's height is less than the current height, we can trap water there. The volume of trapped water is the difference between the current height and the adjacent height. We then add the larger height back to the priority queue and repeat this process until the priority queue is empty.

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

Continue Practicing

#675 cut off trees for golf event #778 swim in rising water #1263 minimum moves to move a box to their target location