LeetCode 407: Trapping Rain Water II Solution

Master LeetCode problem 407 (Trapping Rain Water II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

407. Trapping Rain Water II

Hard

Array Breadth-First Search Heap (Priority Queue)Matrix

Problem Explanation

Explanation:

To solve this problem, we can use a priority queue to store the cells based on their heights. We start by adding all the border cells to the priority queue and mark them as visited. Then, we iterate over the priority queue and process each cell by checking its neighboring cells. If the neighboring cell is lower in height, we can trap water at that cell and update the trapped water volume. We also update the neighboring cell's height to the current cell's height if needed. This process continues until all cells are visited.

Time Complexity: O(m * n * log(m*n))
Space Complexity: O(m * n) :

Solution Code

class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0) {
            return 0;
        }
        
        int m = heightMap.length, n = heightMap[0].length;
        int trappedWater = 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        
        // Add border cells to priority queue
        for (int i = 0; i < m; i++) {
            visited[i][0] = visited[i][n - 1] = true;
            pq.offer(new int[]{i, 0, heightMap[i][0]});
            pq.offer(new int[]{i, n - 1, heightMap[i][n - 1]});
        }
        for (int j = 0; j < n; j++) {
            visited[0][j] = visited[m - 1][j] = true;
            pq.offer(new int[]{0, j, heightMap[0][j]});
            pq.offer(new int[]{m - 1, j, heightMap[m - 1][j]});
        }
        
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            for (int[] dir : dirs) {
                int x = cell[0] + dir[0];
                int y = cell[1] + dir[1];
                if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y]) {
                    trappedWater += Math.max(0, cell[2] - heightMap[x][y]);
                    visited[x][y] = true;
                    pq.offer(new int[]{x, y, Math.max(cell[2], heightMap[x][y])});
                }
            }
        }
        
        return trappedWater;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 407 (Trapping Rain Water II)?

This page provides optimized solutions for LeetCode problem 407 (Trapping Rain Water II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 407 (Trapping Rain Water II)?

The time complexity for LeetCode 407 (Trapping Rain Water II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 407 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 407 in Java, C++, or Python.

Back to LeetCode Solutions