[C++] 8ms solution: min-heap + flood-fill for lakes
This solution is mostly the same as the other solutions discussed, using a min-heap / priority-queue, but with an extra trick to greatly speed up traversal of \
This solution is mostly the same as the other solutions discussed, using a min-heap / priority-queue, but with an extra trick to greatly speed up traversal of \'lakes\'.\n\nRather than push every single grid-point onto the min-heap (an _O(log n)_ operation), we can traverse any self-contained lakes in their entirety when we reach them, using a much cheaper data-structure. A stack, in this case. This works because a lake is effectively a large flat surface, meaning all points have the same height. When we\'re in \'lake-traversal mode\', we\'re essentially performing a flood-fill algorithm (which seems oddly appropriate).\n\n```\nstruct GridPoint {\n  int height;\n  int r;\n  int c;\n};\n\nbool operator>(const GridPoint& a, const GridPoint& b) {\n  return a.height > b.height;\n}\n\nstruct Direction {\n  int r;\n  int c;\n};\n\nconstexpr std::array<Direction, 4> DIRECTIONS = {{\n  {+1,  0},\n  {-1,  0},\n  { 0, +1},\n  { 0, -1}\n}};\n\ntemplate<class T>\nusing MinQueue = std::priority_queue<T, std::vector<T>, std::greater<T>>;\n\nclass Solution {\npublic:\n  int trapRainWater(std::vector<std::vector<int>>& heightMap) {\n    // Set dimensions and allow early bail-out\n    const int R = heightMap.size();\n    if (R <= 2) return 0;\n    const int C = heightMap[0].size();\n    if (C <= 2) return 0;\n    \n    // Traversal data-structures\n    MinQueue<GridPoint> gridTraversal;\n    std::stack<GridPoint> lakeTraversal;\n    \n    // Initialize gridTraversal queue and mark cells as visited;\n    // heightMap doubles as a visited-tracker: -1 = visited\n    heightMap[0][0]     = -1;\n    heightMap[0][C-1]   = -1;\n    heightMap[R-1][0]   = -1;\n    heightMap[R-1][C-1] = -1;\n    for (int r = 1; r < R - 1; ++r) {\n      gridTraversal.push({ heightMap[r][0],   r, 0   });\n      gridTraversal.push({ heightMap[r][C-1], r, C-1 });\n      heightMap[r][0]   = -1;\n      heightMap[r][C-1] = -1;\n    }\n    for (int c = 1; c < C - 1; ++c) {\n      gridTraversal.push({ heightMap[0][c],   0,   c });\n      gridTraversal.push({ heightMap[R-1][c], R-1, c });\n      heightMap[0][c]   = -1;\n      heightMap[R-1][c] = -1;\n    }\n    \n    // Visit all cells systematically from low- to high-ground\n    int trappedRainWater = 0;\n    while (!gridTraversal.empty() || !lakeTraversal.empty()) {\n      GridPoint p;\n      if (lakeTraversal.empty()) {\n        p = gridTraversal.top();\n        gridTraversal.pop();\n      } else {\n        p = lakeTraversal.top();\n        lakeTraversal.pop();\n      }\n      for (const auto& d : DIRECTIONS) {\n        const int nr = p.r + d.r;\n        if (nr < 0 || nr >= R) continue;\n        const int nc = p.c + d.c;\n        if (nc < 0 || nc >= C) continue;\n        if (heightMap[nr][nc] == -1) continue;\n        if (heightMap[nr][nc] <= p.height) {\n          trappedRainWater += p.height - heightMap[nr][nc];\n          lakeTraversal.push({ p.height, nr, nc });\n        } else {\n          gridTraversal.push({ heightMap[nr][nc], nr, nc });\n        }\n        heightMap[nr][nc] = -1;\n      }\n    }\n    return trappedRainWater;\n  }\n};\n\nstatic const auto magic = []() {\n  std::ios::sync_with_stdio(false);\n  std::cin.tie(nullptr);\n  std::cout.tie(nullptr);\n  return nullptr;\n}();\n```
['Heap (Priority Queue)']