LeetCode Daily Problem P407 Trapping Rain Water II

---

Timeline

Timeline

2025-10-03

init

Min-heap, BFS

---

Problem:

P407 Trapping Rain WaterII

https://leetcode.cn/problems/trapping-rain-water-ii/description/?envType=daily-question&envId=2025-10-03

• Boundary cells can never hold water
  Because water flows away from the boundary, the boundary of the pool is the perimeter of the matrix.

• Start filling from the shortest boundary
  Similar to the ‘barrel effect’, the water level is determined by the lowest boundary. Therefore, we need to dynamically maintain the current lowest boundary height.

• Algorithm steps (min-heap + BFS)

  • Put all boundary cells (the entire perimeter) into a min-heap (priority queue, sorted by height from smallest to largest), and mark them as visited.
  • Each time, pop the current lowest cell from the heap, denoted as cell.
  • Scan its 4-directional neighbors:
    • If the neighbor has not been visited: if the neighbor’s height < cell’s height, it means water can accumulate here, and the amount of water is cell height - neighbor height. Update the neighbor’s ‘effective height’ to max(neighbor height, cell height) (after the water fills up, its height is equivalent to the water surface). Add the neighbor to the heap.
  • Repeat until the heap is empty.

Thus, the entire algorithm is equivalent to ‘pouring water inward from the shortest boundary’.

For example

[
  [5,5,5,5],
  [5,1,1,5],
  [5,1,1,5],
  [5,5,5,5]
]

The outer ring heights are all 5, the middle is 1. Starting from the boundary, the lowest height in the heap is 5. When processing the middle cell, it is found that height 1 is lower than the boundary water level 5 → can hold 4 units of water. Each inner cell holds 4, finally getting 4*4=16.

#include <queue>
#include <tuple>
#include <vector>

using std::priority_queue;
using std::tuple;
using std::vector;

typedef priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >,
                       std::greater<tuple<int, int, int> > >
        min_heap;
class Solution {
    public:
        int trapRainWater(vector<vector<int> > &heightMap)
        {
                int m = heightMap.size();
                int n = heightMap[0].size();
                int res = 0;
                min_heap pq;

                vector<vector<bool> > visit(m, vector<bool>(n, false));

                if (m <= 2 || n <= 2) {
                        return 0;
                }
                for (int i = 0; i < m; ++i) {
                        for (int j = 0; j < n; ++j) {
                                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                                        pq.push({ heightMap[i][j], i, j });
                                        visit[i][j] = true;
                                }
                        }
                }

                int dirs[] = { -1, 0, 1, 0, -1 };
                while (!pq.empty()) {
                        auto [h, x, y] = pq.top();
                        pq.pop();
                        // Traverse the top, bottom, left, and right of the heap top
                        for (int k = 0; k < 4; ++k) {
                                int nx = x + dirs[k];
                                int ny = y + dirs[k + 1];
                                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                                        if (heightMap[nx][ny] < h) {
                                                res += h - heightMap[nx][ny];
                                        }
                                        visit[nx][ny] = true;
                                        pq.push({ std::max(heightMap[nx][ny], h), nx, ny });
                                }
                        }
                }

                return res;
        }
};