407. Trapping Rain Water II – Leetcode Solutions

Example 1:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.

Example 2:

Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output: 10

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        # Edge case: If the grid is too small, it cannot trap water
        if not heightMap or len(heightMap) < 3 or len(heightMap[0]) < 3:
            return 0
        
        # Dimensions of the grid
        m, n = len(heightMap), len(heightMap[0])
        
        # Min-heap to process cells in order of height
        heap = []
        
        # Visited array to track processed cells
        visited = [[False] * n for _ in range(m)]
        
        # Add all boundary cells to the heap
        for i in range(m):
            for j in [0, n - 1]:  # Left and right boundaries
                heapq.heappush(heap, (heightMap[i][j], i, j))
                visited[i][j] = True
        for j in range(n):
            for i in [0, m - 1]:  # Top and bottom boundaries
                heapq.heappush(heap, (heightMap[i][j], i, j))
                visited[i][j] = True
        
        # Directions for neighbor traversal (up, down, left, right)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        # Total water trapped
        water_trapped = 0
        
        # Process the heap
        while heap:
            height, x, y = heapq.heappop(heap)
            
            # Check all neighbors
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                # Skip if out of bounds or already visited
                if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[nx][ny]:
                    continue
                
                # Calculate water trapped at the neighbor
                trapped = max(0, height - heightMap[nx][ny])
                water_trapped += trapped
                
                # Update the neighbor's height and mark as visited
                new_height = max(height, heightMap[nx][ny])
                heapq.heappush(heap, (new_height, nx, ny))
                visited[nx][ny] = True
        
        return water_trapped

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        // Edge case: If the map is too small to trap water
        if (heightMap.empty() || heightMap[0].empty() || heightMap.size() < 3 || heightMap[0].size() < 3)
            return 0;

        int m = heightMap.size(); // Number of rows
        int n = heightMap[0].size(); // Number of columns

        // Min-heap to keep track of boundary cells
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> minHeap;

        // Visited matrix to mark the cells that have been processed
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        // Add all boundary cells into the min-heap
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    minHeap.push({heightMap[i][j], {i, j}});
                    visited[i][j] = true;
                }
            }
        }

        // Directions for exploring neighboring cells (up, down, left, right)
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        int trappedWater = 0;

        // Process cells in the min-heap
        while (!minHeap.empty()) {
            auto [currentHeight, cell] = minHeap.top();
            minHeap.pop();

            int x = cell.first;
            int y = cell.second;

            // Explore the neighboring cells
            for (auto& dir : directions) {
                int nx = x + dir.first;
                int ny = y + dir.second;

                // Check if the neighbor is within bounds and not visited
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    // Calculate the water trapped at the neighboring cell
                    trappedWater += max(0, currentHeight - heightMap[nx][ny]);

                    // Update the height of the neighboring cell to maintain the water level
                    minHeap.push({max(currentHeight, heightMap[nx][ny]), {nx, ny}});
                    visited[nx][ny] = true;
                }
            }
        }

        return trappedWater;
    }
};

var trapRainWater = function(heightMap) {
    // Base case: if the matrix is too small to trap water, return 0
    if (heightMap.length < 3 || heightMap[0].length < 3) return 0;

    const rows = heightMap.length;
    const cols = heightMap[0].length;
    let trappedWater = 0;

    // Min-Heap to track the current lowest boundary
    const minHeap = [];
    const visited = Array.from({ length: rows }, () => Array(cols).fill(false));

    // Helper to add boundary cells to the heap
    const addToHeap = (row, col) => {
        minHeap.push([heightMap[row][col], row, col]);
        visited[row][col] = true;
    };

    // Push all boundary cells into the min-heap and mark them visited
    for (let r = 0; r < rows; r++) {
        addToHeap(r, 0); // First column
        addToHeap(r, cols - 1); // Last column
    }
    for (let c = 1; c < cols - 1; c++) {
        addToHeap(0, c); // First row (excluding corners)
        addToHeap(rows - 1, c); // Last row (excluding corners)
    }

    // Min-heapify the heap (custom comparator for JavaScript array)
    minHeap.sort((a, b) => a[0] - b[0]);

    // Define four possible directions to move
    const directions = [
        [0, 1],  // Right
        [1, 0],  // Down
        [0, -1], // Left
        [-1, 0]  // Up
    ];

    // Process cells in the min-heap
    while (minHeap.length > 0) {
        // Pop the cell with the lowest height
        const [height, row, col] = minHeap.shift();

        // Explore all adjacent cells
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;

            // Skip cells that are out of bounds or already visited
            if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || visited[newRow][newCol]) {
                continue;
            }

            // Calculate the water trapped at this cell (if any)
            const waterHeight = Math.max(0, height - heightMap[newRow][newCol]);
            trappedWater += waterHeight;

            // Update the cell height and add it to the heap
            const newHeight = Math.max(height, heightMap[newRow][newCol]);
            minHeap.push([newHeight, newRow, newCol]);
            visited[newRow][newCol] = true;
        }

        // Re-heapify the heap to maintain the min-heap property
        minHeap.sort((a, b) => a[0] - b[0]);
    }

    return trappedWater;
};

class Solution {
    public int trapRainWater(int[][] heightMap) {
        // If the height map has less than 3 rows or columns, no water can be trapped
        if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
            return 0;
        }

        int m = heightMap.length; // Number of rows
        int n = heightMap[0].length; // Number of columns
        boolean[][] visited = new boolean[m][n]; // Tracks if a cell has been processed
        PriorityQueue<Cell> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.height, b.height)); // Min-heap for processing cells by height

        // Add all border cells to the min-heap and mark them as visited
        for (int i = 0; i < m; i++) {
            minHeap.offer(new Cell(i, 0, heightMap[i][0]));
            minHeap.offer(new Cell(i, n - 1, heightMap[i][n - 1]));
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }
        for (int j = 0; j < n; j++) {
            minHeap.offer(new Cell(0, j, heightMap[0][j]));
            minHeap.offer(new Cell(m - 1, j, heightMap[m - 1][j]));
            visited[0][j] = true;
            visited[m - 1][j] = true;
        }

        int trappedWater = 0; // Accumulates the total water trapped
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Directions for adjacent cells (right, down, left, up)

        // Process cells in the heap
        while (!minHeap.isEmpty()) {
            Cell cell = minHeap.poll(); // Get the cell with the smallest height

            for (int[] dir : directions) {
                int newRow = cell.row + dir[0];
                int newCol = cell.col + dir[1];

                // Check if the adjacent cell is within bounds and not visited
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;

                    // Water trapped in the current cell is the difference between the boundary height and the adjacent cell height
                    trappedWater += Math.max(0, cell.height - heightMap[newRow][newCol]);

                    // Add the adjacent cell to the heap with an updated height (max of current height or adjacent cell height)
                    minHeap.offer(new Cell(newRow, newCol, Math.max(cell.height, heightMap[newRow][newCol])));
                }
            }
        }

        return trappedWater; // Return the total trapped water
    }
}

// Helper class to represent a cell in the height map
class Cell {
    int row, col, height;

    Cell(int row, int col, int height) {
        this.row = row;
        this.col = col;
        this.height = height;
    }
}