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 store water.
  Because water flows away from the boundary, the boundary of the pool is the perimeter of the matrix.

• Start filling from the lowest 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 surrounding ring) into a min-heap (priority queue, sorted by height in ascending order), and mark them as visited.
  • Each time, pop the current lowest cell from the heap, denoted as cell.
  • Scan its neighbors in 4 directions:
    • If the neighbor has not been visited: if the neighbor’s height < cell’s height, 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.

In this way, the whole 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, and the middle is 1. Starting from the boundary, the lowest height in the heap is 5. When processing the middle cell, we find height 1, which is lower than the boundary water level 5 → it can hold 4 units of water. Each inner cell holds 4, and finally we get 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 up, down, left, and right neighbors 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;
        }
};