Trapping Rain Water II - Simplified (Java)
Trapping Rain Water II - Heap + Matrix\n\nProblem Statement\n\nGiven an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevati
### Trapping Rain Water II - Heap + Matrix\n\n**Problem Statement**\n\nGiven an m x n integer matrix `heightMap` representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.\n\n**Intuition**\n\nTo solve the problem of trapping rainwater in a 2D elevation map, we need to approach it by considering the boundary cells and progressively examining inner cells. The cells at the boundary form a natural barrier for water retention. By processing the lowest cells first, we can effectively determine the amount of water that can be trapped by surrounding higher cells.\n\nThe key idea is to use a min-heap to keep track of the cells by their height. Starting from the boundary cells, we use a breadth-first search (BFS) approach to explore the neighboring cells. For each cell, we calculate the potential water it can trap based on the difference between its height and the heights of its neighbors. If a neighbor is lower, it can trap water up to the height of the current cell. This approach ensures that we process cells in increasing order of their heights, allowing us to accurately determine the trapped water.\n\n**Function trapRainWater:**\n\n1. Initialize a min-heap to store cells in ascending order based on their heights.\n2. Initialize a marked matrix to keep track of processed cells.\n3. Mark the boundary cells and add them to the min-heap using the `markBoundaries` function.\n4. Calculate the total trapped water using the `trappedWaterInTopology` function, which processes cells from the min-heap and explores their neighbors.\n\n```java\nclass Solution {\n    // Heap to store the cells according to their increasing height...\n    PriorityQueue<int[]> minHeap;\n    // Matrix to mark the cells that are processed...\n    boolean marked[][];\n\n    public int trapRainWater(int[][] heightMap) {\n        int m = heightMap.length, n = heightMap[0].length;\n        // MinHeap to store in ascending order based on heights...\n        minHeap = new PriorityQueue<>(Comparator.comparingInt(cell -> cell[2]));\n        marked = new boolean[m][n];\n        markBoundaries(heightMap);  // Filling the boundary cells into the minheap...\n        return trappedWaterInTopology(heightMap);   // Returning the retained water...\n    }\n```\n\n**Function markBoundaries:**\n\n1. Iterate over all rows and mark the first and last columns as boundary cells.\n2. Iterate over all columns and mark the first and last rows as boundary cells.\n3. Add these boundary cells to the min-heap and mark them as processed in the `marked` matrix.\n\n```java\n    public void markBoundaries(int[][] map) {\n        int m = map.length, n = map[0].length;\n        // Marking the rows...\n        for (int i = 0; i < m; i++) {\n            minHeap.add(new int[]{i, 0, map[i][0]});\n            marked[i][0] = true;\n            minHeap.add(new int[]{i, n - 1, map[i][n - 1]});\n            marked[i][n - 1] = true;\n        }\n        // Marking the columns...\n        for (int j = 0; j < n; j++) {\n            minHeap.add(new int[]{0, j, map[0][j]});\n            marked[0][j] = true;\n            minHeap.add(new int[]{m - 1, j, map[m - 1][j]});\n            marked[m - 1][j] = true;\n        }\n    }\n```\n\n**Function trappedWaterInTopology:**\n\n1. Initialize a variable `water` to store the total trapped water.\n2. Use a directions array to explore the neighboring cells in four cardinal directions.\n3. While the min-heap is not empty, process the cell with the lowest height.\n4. For each neighboring cell, if it has not been processed, calculate the potential trapped water and update the height in the min-heap.\n5. Add the neighbor to the min-heap and mark it as processed.\n\n```java\n    public int trappedWaterInTopology(int[][] map) {\n        int m = map.length, n = map[0].length;\n        int water = 0;  // Variable to store the amount of water retained...\n        int[][] direction = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n        \n        while (!minHeap.isEmpty()) {\n            int[] cell = minHeap.poll();\n            int x = cell[0], y = cell[1], height = cell[2];\n            \n            for (int[] dir : direction) {\n                int newRow = x + dir[0], newCol = y + dir[1];\n                if (newRow >= 0 && newCol >= 0 && newRow < m && newCol < n && !marked[newRow][newCol]) {\n                    marked[newRow][newCol] = true;  // Mark the cell...\n                    water += Math.max(0, height - map[newRow][newCol]);  // Calculate trapped water...\n                    // Add the neighbor cell with updated height...\n                    minHeap.add(new int[]{newRow, newCol, Math.max(height, map[newRow][newCol])});\n                }\n            }\n        }\n        \n        return water;  // Returning the total water stored...\n    }\n}\n```\n\n**Complexity**\n\n- **Time Complexity:** The time complexity is `O(m * n * log(m * n))`, where `m` is the number of rows and `n` is the number of columns. This accounts for processing each cell and performing heap operations.\n- **Space Complexity:** The space complexity is `O(m * n)` for the marked matrix and the min-heap.\n
['Java']