| Beats 90% | BFS + Min. Heap Java Solution
IntuitionThe first thing that comes to mind is, of course, to start with the side cells, because you can't have water in them.
Determining the amount of water t
# Intuition
The first thing that comes to mind is, of course, to start with the side cells, because you can't have water in them.
Determining the amount of water that the next cell can trap is also quite simple - it's just the difference in height (we will always determine the correct amount of water because we took the cell from the heap with the minimum height).
We need to understand that we can immediately add this value to the final result, because depending on the height of the neighboring cells, the total amount of water that will be trapped may increase, but not decrease.
The next thing to do is to add this cell with water to our heap as if it were a cell without water with the correct height. And like this BFS and Min. Heap will do all the work.

# Approach
`Vertex` class is needed for more convenient work with `PriorityQueue` and better readability of the code.

1) Let's run through the side cells, mark them as `visited`, and add them to our heap.
2) BFS approach :
    * Explore the neighbouring cells of the popped cell
    * Calculate how much water it can trap = `max(0, height - heightMap[nextX][nextY])`. Add this value to our `result`.
    * Add the cell to the heap with `height = max(height, heightMap[nextX][nextY])`
    * Mark the neighbouring cell as visited
 

# Complexity
- Time complexity:
$$O(m * n * log(m * n))$$

- Space complexity:
$$O(m * n)$$

# Code
```java []
class Solution {
    private class Vertex implements Comparable<Vertex> {
        public int height;
        public int x, y;

        Vertex(int height, int x, int y) {
            this.height = height;
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Vertex o) {
            return this.height - o.height;
        }
    }

    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        PriorityQueue<Vertex> pq = new PriorityQueue<>();
        boolean[][] visited = new boolean[m][n];
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        int result = 0;

        for (int i = 0; i < m; i++) {
            visited[i][0] = true;
            visited[i][n - 1] = true;
            pq.offer(new Vertex(heightMap[i][0], i, 0));
            pq.offer(new Vertex(heightMap[i][n - 1], i, n - 1));
        }

        for (int i = 0; i < n; i++) {
            visited[0][i] = true;
            visited[m - 1][i] = true;
            pq.offer(new Vertex(heightMap[0][i], 0, i));
            pq.offer(new Vertex(heightMap[m - 1][i], m - 1, i));
        }

        while(!pq.isEmpty()) {
            Vertex curr = pq.poll();
            int height = curr.height, x = curr.x, y = curr.y;

            for (int i = 0; i < 4; i++) {
                int nextX = x + directions[i][0], nextY = y + directions[i][1];

                if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && !visited[nextX][nextY]) {
                    result += Math.max(0, height - heightMap[nextX][nextY]);
                    pq.offer(new Vertex(Math.max(height, heightMap[nextX][nextY]), nextX, nextY));
                    visited[nextX][nextY] = true;
                }
            }
        }

        return result;
    }
}
```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Java']