Java | Code with comments | Using MinHeap (Priority Queue ADT)
INTUITION:\nThe reason approach of finding greatest height on Left, Right, Up and Down won\'t work is that water can flow in any Right-Left-Down-Up combination.
**INTUITION:**\nThe reason approach of finding greatest height on Left, Right, Up and Down won\'t work is that water can flow in any Right-Left-Down-Up combination.\nOne such flow is RRRDDRDDR (each character represents one unit of water flow in respective direction).\n\n**Approach:**\nWe start from boundary of the input since that\'s what decides whether water would flow out of the structure or not. And if we notice, the minimum height on the boundary is the deciding factor. That\'s where intuition to use min heap comes in the picture.\n\nAs we move along, boundary keeps moving in.\n\nRest of the steps involve handling 3 cases while exploring neighbors:\n1. Height of neighbor < height of boundary element\n2. Height of neighbor == height of boundary element\n3. Height of neighbor > height of boundary element\n\nCode has comments to explain the inner details of iterating over neighbors.\n\n```\nclass HeapEntry {\n    int x;\n    int y;\n    int height;\n    \n    public HeapEntry(int x, int y, int height) {\n        this.x = x;\n        this.y = y;\n        this.height = height;\n    }\n}\n\nclass Solution {\n    \n    int[] dx = {0, -1, 0, 1};\n    int[] dy = {-1, 0, 1, 0};\n    \n    int newX = 0, newY = 0;\n    \n    private void processBoundary(int[][] heightMap, boolean[][] visited, PriorityQueue<HeapEntry> minHeap) {\n        int n = heightMap.length;\n        int m = heightMap[0].length;\n        \n        //first and last column\n        for(int i = 0; i<n; i++) {\n            //first column\n            visited[i][0] = true;\n            minHeap.add(new HeapEntry(i, 0, heightMap[i][0]));\n            \n            //last column\n            visited[i][m-1] = true;\n            minHeap.add(new HeapEntry(i, m-1, heightMap[i][m-1]));\n        }\n        \n        //first and last row\n        for(int j = 0; j<m; j++) {\n            //first row\n            visited[0][j] = true;\n            minHeap.add(new HeapEntry(0, j, heightMap[0][j]));\n            \n            //last row\n            visited[n-1][j] = true;\n            minHeap.add(new HeapEntry(n-1, j, heightMap[n-1][j]));\n        }\n    }\n    \n    private boolean isSafe(int[][] heightMap, boolean[][] visited, int x, int y) {\n        int n = heightMap.length;\n        int m = heightMap[0].length;\n        \n        if(x<0 || x>=n || y<0 || y>=m) {\n            return false;\n        }\n        \n        return visited[x][y] == false;\n    }\n    \n    public int trapRainWater(int[][] heightMap) {\n        if(heightMap == null || heightMap.length == 0) {\n            return 0;\n        }\n        \n        int n = heightMap.length; //rows\n        int m = heightMap[0].length; //columns\n        \n        boolean[][] visited = new boolean[n][m];\n        \n        //min heap, based on height\n        PriorityQueue<HeapEntry> minHeap = new PriorityQueue<>((i1, i2) -> (i1.height - i2.height));\n        \n        int totalTrappedWater = 0;\n        \n        //process boundary\n        processBoundary(heightMap, visited, minHeap);\n        \n        HeapEntry heapEntry = null;\n        int x = 0, y = 0, height = 0;\n        while(!minHeap.isEmpty()) {\n            heapEntry = minHeap.poll();\n            \n            x = heapEntry.x;\n            y = heapEntry.y;\n            height = heapEntry.height;\n            \n            //explore 4 neighbors\n            for(int k = 0; k<4; k++) {\n                newX = x + dx[k];\n                newY = y + dy[k];\n                \n                if(isSafe(heightMap, visited, newX, newY)) {\n                    //mark new position as visited\n                    visited[newX][newY] = true;\n                    \n                    //3 cases\n                    if(heightMap[newX][newY] < height) {\n                        //comparing with height, not heightMap[x][y] because it gets replaced when we add to heaps in following 3 cases\n                        \n                        totalTrappedWater += height - heightMap[newX][newY];\n                        //put the entry to heap\n                        minHeap.add(new HeapEntry(newX, newY, height));\n                    } else if(heightMap[newX][newY] == height) {\n                        //no change to trapped water\n                        //put the entry to heap\n                        minHeap.add(new HeapEntry(newX, newY, height));\n                    } else {\n                        //heightMap[newX][newY] > height\n                        //no change to trapped water\n                        //put entry to heap\n                        minHeap.add(new HeapEntry(newX, newY, heightMap[newX][newY]));\n                    }\n                }\n            }\n        }\n        \n        return totalTrappedWater;\n    }\n}\n\n```
['Java']