✅✅Beats 100%🔥C++🔥Python|| 🚀🚀Super Simple and Efficient Solution🚀🚀||🔥Python🔥C++✅✅
Complexity
Time complexity:O(mnlogmn)

Space complexity:O(mn)
Code

# Complexity
- Time complexity:$$O(mn log mn)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:$$O(mn)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
struct T {
  int i;
  int j;
  int h;  
};
class Solution {
 public:
  int trapRainWater(vector<vector<int>>& heightMap) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = heightMap.size();
    const int n = heightMap[0].size();
    int ans = 0;
    auto compare = [](const T& a, const T& b) { return a.h > b.h; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
    vector<vector<bool>> seen(m, vector<bool>(n));
    for (int i = 0; i < m; ++i) {
      minHeap.emplace(i, 0, heightMap[i][0]);
      minHeap.emplace(i, n - 1, heightMap[i][n - 1]);
      seen[i][0] = true;
      seen[i][n - 1] = true;
    }
    for (int j = 1; j < n - 1; ++j) {
      minHeap.emplace(0, j, heightMap[0][j]);
      minHeap.emplace(m - 1, j, heightMap[m - 1][j]);
      seen[0][j] = true;
      seen[m - 1][j] = true;
    }
    while (!minHeap.empty()) {
      const auto [i, j, h] = minHeap.top();
      minHeap.pop();
      for (const auto& [dx, dy] : dirs) {
        const int x = i + dx;
        const int y = j + dy;
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (seen[x][y])
          continue;
        if (heightMap[x][y] < h) {
          ans += h - heightMap[x][y];
          minHeap.emplace(x, y, h); 
        } else {
          minHeap.emplace(x, y, heightMap[x][y]);
        }
        seen[x][y] = true;
      }
    }
    return ans;
  }
};
```
```python3 []
class Solution:
  def trapRainWater(self, heightMap: list[list[int]]) -> int:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(heightMap)
    n = len(heightMap[0])
    ans = 0
    minHeap = []
    seen = set()
    for i in range(m):
      heapq.heappush(minHeap, (heightMap[i][0], i, 0))
      heapq.heappush(minHeap, (heightMap[i][n - 1], i, n - 1))
      seen.add((i, 0))
      seen.add((i, n - 1))
    for j in range(1, n - 1):
      heapq.heappush(minHeap, (heightMap[0][j], 0, j))
      heapq.heappush(minHeap, (heightMap[m - 1][j], m - 1, j))
      seen.add((0, j))
      seen.add((m - 1, j))
    while minHeap:
      h, i, j = heapq.heappop(minHeap)
      for dx, dy in dirs:
        x = i + dx
        y = j + dy
        if x < 0 or x == m or y < 0 or y == n:
          continue
        if (x, y) in seen:
          continue
        if heightMap[x][y] < h:
          ans += h - heightMap[x][y]
          heapq.heappush(minHeap, (h, x, y))
        else:
          heapq.heappush(minHeap, (heightMap[x][y], x, y))
        seen.add((x, y))

    return ans
```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Matrix', 'C++', 'Python3']