Beats 95.51% ✅ || Explanation of the Intuition behind Priority Queue 
IntuitionFirst Intuition :The first thing that comes in my mind after reading the problem the is same approach that i used in Trapping Rain Water, where i just
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
### First Intuition :
The first thing that comes in my mind after reading the problem the is same approach that i used in [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/submissions/1022016547/), where i just keep track of next greater and prev greater elements and for each height calculate answer by taking mininmum among these maxmimum. I though in the same way, if i can keep the track of the rowwise and column wise greatest elements, i.e. next greatest rowwise, then next greatest column wise and prev greatest rowwise and prev greatest column wise, then compute answer for each internal elements. Your can see that code [here](https://leetcode.com/problems/trapping-rain-water-ii/submissions/1515272741/).
But the approach *fail*, as water can flows out from any where , any boundary :\\
For this test:

[[12,13,1,12],
[13,**4,13**,12],
[13,**8,10**,12],
[12,**13**,**12**,12],
[13,13,13,13]]

we calculate for all the bold marked heights, the water it can store.
For 4 we are assuming it can store 13 water level, but it is wrong, as water flow out from (1,1) -> (2,1) -> (2, 2) -> (2, 3) , assuming 0 based indexing.

### 2nd Intuition
From the first intution, it seems like there is some kind of flow (dfs/ bfs), along with that we need to track of minimum height first so that maximum height will be processes later. This leads me to Minimum priority queue. As Boundaries will never store water(they will be the wall for internal elements), can we start up with storing the boundaries in the min priority_queue(similar to multisource bfs) and then perform some operation?


# Approach
<!-- Describe your approach to solving the problem. -->
Step 1: Store all the boundary elements with their height in minimum priority queue and mark them all visited.
Step 2: One by one pop out each boundary elements and process its internals.
Step 3: If any internal element that is neighbour of the boundary has height less than the boundary's height, then water can be filled in the internal and we will increment the result by the difference of their height.
Step 4: If any internal that is neighbour of the boundary has height greater than or equal to the boundary height then it cannot store water.
Step 5: We will push the maximum height among the two neighbour in the queue for further processing and mark the adjacent as visited.
Step 6: Finally we will return the result after each element is processes.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
*O(m * n * log(m * n))* 
All the nodes will be pushed in the priority and each are processes.

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

# Code
```cpp []
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int n = heightMap.size();
        int m = heightMap[0].size();
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                       greater<pair<int, int>>>
            pq;

        vector<int> dir = {0, -1, 0, 1, 0};
        vector<vector<int>> vis(n, vector<int>(m, 0));
        // Push all the boundary elements of left and right
        for (int i = 0; i < n; i++) {
            vis[i][0] = vis[i][m - 1] = 1;
            pq.push({heightMap[i][0], i * m});
            pq.push({heightMap[i][m - 1], i * m + m - 1});
        }
       // Push all the boundary elements of top and bottom
        for (int j = 0; j < m; j++) {
            vis[0][j] = vis[n - 1][j] = 1;
            pq.push({heightMap[0][j], j});
            pq.push({heightMap[n - 1][j], n * m - m + j});
        }
        int res = 0;
        while (pq.empty() == false) {
            // pop out the boundary element
            int val = pq.top().first;
            int block1 = pq.top().second;
            pq.pop();
            // move to all the adjacent elements of boundary 
            for (int k = 0; k <= 3; k++) {
                int newr = block1 / m + dir[k];
                int newc = block1 % m + dir[k + 1];
                int newblock = newr * m + newc;
                // the adjacent cell is not visited
                if (newr > 0 && newr < n - 1 && newc > 0 && newc < m - 1 && vis[newr][newc] == 0) {
                    // Mark the adjacent visited
                    vis[newr][newc] = 1;
                    // Height of the parent is greater then increment the result but wise don't increment 
                    res += (val > heightMap[newr][newc])
                               ? (val - heightMap[newr][newc])
                               : 0;
                    // Push the adjacent with the maximum height
                    pq.push({max(heightMap[newr][newc], val), newblock});
                }
            }
        }
        return res;
    }
};
```
['Breadth-First Search', 'Heap (Priority Queue)', 'Matrix', 'C++']