Why Brute doesn't work? Explained. Used Flood Fill Algo, Beats 94 %
IntuitionWhy Brute Force of taking min of maximum walls in all 4 directions, doesn't work?
Let's take this example>
[12,13,1,12]
[13,4,13,12]
[13,8,10,12]
[12,1
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Why Brute Force of taking min of maximum walls in all 4 directions, doesn't work?
Let's take this example>
[12,13,1,12] 
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]

Here at first it seems like the answer is 15, the cell with 4 will contain 9 amounts of water, 8 will contain 4, and 10 will contain 2.
But the tricky part is, 4 will contain 8 and not 9. Why?
See it as a drainage, if you store 9 amounts of water in the cell containing 4, the water will seep out through, the next row last column containg 12 (cell -> 2, 3). Realised the issue?
So Taking Maximum walls in all 4 direction and then taking minimum of 4, and then subtracting it with current height to add in the answer is incorrect.

# Brute Force(Logically Incorrect)
```cpp []
class Solution {
public:
    int trapRainWater(vector<vector<int>> &arr) {


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


        int n = arr.size(), m = arr[0].size(), water = 0;

        for(int i = 1; i < n - 1; i++){

            for(int j = 1; j < m - 1; j++){


                int right = 0, left = 0, up = 0, down = 0;
                
                for(int col = j + 1; col < m; col++)    right = max(right, arr[i][col]);
                for(int row = i + 1; row < n; row++)    down = max(down, arr[row][j]);
                for(int col = j - 1; col >= 0; col--)   left = max(left, arr[i][col]);
                for(int row = i - 1; row >= 0; row--)    up = max(up, arr[row][j]);

                water += max(min({left, right, up, down}) - arr[i][j], 0);
            }
        }

        return water;
    }
};
```

# Approach
<!-- Describe your approach to solving the problem. -->
So what to do?
Instead of starting from inside, we will start from boundaries, and will apply flood fill algorithm (Fancy name but its simple).
As we saw, the water seeped out through cell (2, 3) in above case, we will start from boundaries and start marking their N4 neighbours with the maximum of border to that wall itself (The taller walls will act as a barrier and wont be affected but the smaller ones will be restricted to hold water not more than this wall height (capping the amount of water that cell could have hold)).
This can be done by Simple BFS, But here we have to keep in mind, that Priority Queue is necessary, as its efficient to start from the smallest wall, as it is the most vulnerable to leaking, and as we are taking Priority queue, we are guaranteed that we wont find any better (storing more/less water) answer for the particular cell.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O((n * m) * log(n * m))
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(n * m)
# Code
```cpp []
#define tiii tuple < int , int , int > 
class Solution {
public:

    bool safe(int i, int j, int m, int n){

        return (i >= 0 && i < n && j >= 0 && j < m);
    }
    int trapRainWater(vector<vector<int>> &arr) {

        int n = arr.size(), m = arr[0].size(), water = 0;
        int delta[] = {-1, 0, 1, 0, -1};

        priority_queue < tiii, vector < tiii >, greater < tiii > > pq;
        vector < vector < int > > visited(n, vector < int > (m, 0));

        for(int i = 0; i < n; i++){ // vertical Boundaries

            pq.push({arr[i][0], i, 0}) , pq.push({arr[i][m - 1], i, m - 1});
            visited[i][0] = visited[i][m - 1] = 1;
        }

        for(int j = 1; j < m - 1; j++){ // horizontal Boundaries

            pq.push({arr[0][j], 0, j}) , pq.push({arr[n - 1][j], n - 1, j});
            visited[0][j] = visited[n - 1][j] = 1;
        }

        while(!pq.empty()){

            auto [height, x, y] = pq.top();
            pq.pop();

            for(int del = 0; del < 4; del++){

                int newx = x + delta[del], newy = y + delta[del + 1];

                if(safe(newx, newy, m, n) && !visited[newx][newy]){
                    
                    visited[newx][newy] = 1;

                    water += max(height - arr[newx][newy], 0); // Adding the difference into water directly, as we are sure that there is no chance that we will get more water for this cell, as even if we try to put more water, it will leak from the cell we are woking on.
                    pq.push({max(arr[newx][newy], height), newx, newy});
                }
            }
        }

        return water;
    }
};
```
['Breadth-First Search', 'Heap (Priority Queue)', 'C++']