Java AC Solution using PriorityQueue with Detailed explanations
First let\'s look at the rationale of this solution: \nIn this 2D container, it is only possible to drap water if any exterior wall cells are higher than at lea
First let\'s look at the rationale of this solution: \nIn this 2D container, it is only possible to drap water if any exterior wall cells are higher than at least one cell inside the container. \n\n\n|XXXXXXXXXXX|\n-----------\n\nThe exterior wall cells are represented using the  - and | as the graph above. \n1. We traverse the entire wall cells in the matrix and store each coordinates and its height in the matrix in their accending order. \n2. From each wall cell, we can then do a BFS traverse and find out wheher the current interior cell height is lower than the wall cell. If it is lower, we can accumulate the difference to the final result. If it is not, we simply skip. For the BFS traversal, we can go UP, DOWN, LEFT, and RIGHT. And to avoid redundancy, we will use a boolean matrix with the same height and width to determine wheter we have visited this cell before.  \n3. After each BFS traversal, we will have to store the visited cell with its coordinates and updated height. Here, the updated height will not neccessarily be the height value in the original 2D matrix but it will be the greater value between the original value in the 2D matrix and its ancestor. Think about this is like, if we have visited this cell, we store the parameters of this cell and we regard this cell as a wall cell for the futher traversal. \n4. In order to maintain the sorted order for the height value, a min-Heap is a good candidate. \nTime Complexity: m:matrix height, n: matrix width --> step1: O(m*n*log(2m+2n-4)) = O(m*n*log(m+n))\nSpace Complexity: boolean matrix and PriorityQueue--> O(m*n)\n\n```\nclass Solution {\n    class Tuple{\n        int x;\n        int y;\n        int height;\n        public Tuple(int x, int y, int height){\n            this.x =x ;\n            this.y =y;\n            this.height = height;\n        }\n    }\n    public int trapRainWater(int[][] heightMap) {\n        if(heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) return 0;\n        int m = heightMap.length;\n        int n = heightMap[0].length;\n        boolean[][] visited = new boolean[m][n];\n        PriorityQueue<Tuple> pq = new PriorityQueue<>((a,b)->(a.height - b.height));\n        for(int i = 0; i<m;i++){\n            for(int j = 0; j<n; j++){\n                if(i==0 || j==0 || i == m-1 || j == n-1){\n                    visited[i][j] = true;\n                    pq.offer(new Tuple(i,j,heightMap[i][j]));\n                }\n            }\n        }\n        int[][] dirs = new int[][]{\n            {0,1},{1,0},{0,-1},{-1,0}\n        };\n        int res = 0;\n        while(!pq.isEmpty()){\n            Tuple cur = pq.poll();\n            for(int i = 0 ; i<dirs.length; i++){\n                int newX = cur.x + dirs[i][0];\n                int newY = cur.y + dirs[i][1];\n                if(newX < 0 || newY <0 || newX>=m || newY>=n || visited[newX][newY]){\n                    continue;\n                }\n                visited[newX][newY] = true;\n                res += Math.max(0,cur.height - heightMap[newX][newY]);\n                pq.offer(new Tuple(newX,newY,Math.max(heightMap[newX][newY],cur.height)));\n            }\n            \n            \n        }\n        return res;\n    }\n}\n```
[]