C++ || Priority Queue 💯✨ || O(m*n (log m*n)) TC ⚡🎓 | Easy to Grasp 🎯✔️
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about trapping rainwater in a 2D height map where each cell has a height
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about trapping rainwater in a 2D height map where each cell has a height. The goal is to compute the amount of water that can be trapped between walls formed by the heights of cells.\n\nThe core idea here is that water can only be trapped between walls that are taller than the cell we\'re considering. This is similar to the 1D "trapping rainwater" problem, but extended to 2D. We need to consider how water can flow from the inside cells to the boundary, and to do that, we use a priority queue to process cells starting from the boundaries (lowest height first).\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Boundary First Processing:\n    - Water will not be trapped at the boundary cells, so we first push all the boundary cells into a min-heap (priority queue). The boundary forms a "container" for the inner cells.\n2. Heap (Priority Queue) for BFS:\n    - We use a priority queue (min-heap) to always process the cell with the lowest height first. This ensures that we calculate trapped water correctly, as water can\'t flow from a higher height to a lower one.\n3. BFS Traversal:\n    - After initializing the boundary, we process the neighboring cells of the current lowest height cell in the priority queue. For each neighboring cell, we calculate the trapped water if the current cell is taller than the neighbor, and then add the taller of the two heights (current or neighbor) back to the priority queue.\n4. Visited Cells:\n- We maintain a visited array to avoid reprocessing cells.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(m * n log(m * n))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(m * n)\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    // Function to check if the given cell (i, j) is within bounds\n    bool isSafe(int i, int j, int m, int n) {\n        return i >= 0 && i < m && j >= 0 && j < n;\n    }\n\npublic:\n    int trapRainWater(vector<vector<int>>& heightMap) {\n        // Get the number of rows (m) and columns (n)\n        int m = heightMap.size();\n        int n = heightMap[0].size();\n\n        // Create a 2D visited array initialized to false\n        vector<vector<bool>> visited(m, vector<bool>(n, false));\n\n        // Priority queue (min-heap) to always process the cell with the minimum height\n        priority_queue<pair<int, pair<int, int>>, \n                       vector<pair<int, pair<int, int>>>, \n                       greater<pair<int, pair<int, int>>>> pq;\n\n        // Add all the boundary cells to the priority queue and mark them as visited\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                // Boundary cells (first row, last row, first column, last column)\n                if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {\n                    pq.push({heightMap[i][j], {i, j}});\n                    visited[i][j] = true;\n                }\n            }\n        }\n\n        // Directions array for moving up, down, left, and right\n        vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n\n        int water = 0;  // To keep track of the total trapped water\n\n        // Process cells in the priority queue\n        while (!pq.empty()) {\n            auto p = pq.top();  // Get the cell with the smallest height\n            pq.pop();\n\n            int height = p.first;  // Height of the current cell\n            int row = p.second.first;  // Row of the current cell\n            int col = p.second.second;  // Column of the current cell\n\n            // Check all four possible directions\n            for (auto& dir : directions) {\n                int nextRow = row + dir[0];\n                int nextCol = col + dir[1];\n\n                // If the neighboring cell is within bounds and not visited\n                if (isSafe(nextRow, nextCol, m, n) && visited[nextRow][nextCol] == false) {\n                    // Calculate water trapped at this neighboring cell\n                    water += max(0, height - heightMap[nextRow][nextCol]);\n\n                    // Push the next cell with the max of its own height or the current height\n                    pq.push({max(height, heightMap[nextRow][nextCol]), {nextRow, nextCol}});\n\n                    // Mark the neighboring cell as visited\n                    visited[nextRow][nextCol] = true;\n                }\n            }\n        }\n\n        // Return the total trapped water\n        return water;\n    }\n};\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'C++']