Given 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.
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
Constraints:
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 104Problem Overview: You are given a 2D grid where each cell represents elevation. After rainfall, water can be trapped between taller boundary cells. The task is to compute how many total units of water remain trapped after the system stabilizes.
Approach 1: Min-Heap Priority Queue + BFS (O(mn log(mn)) time, O(mn) space)
This problem behaves like filling water from the outside boundary inward. Start by pushing all boundary cells into a min-heap. The heap always expands from the lowest boundary height first. Pop the lowest cell, explore its four neighbors using a BFS-style traversal, and determine whether water can be trapped there. If a neighbor is lower than the current boundary height, the difference is trapped water. Push the neighbor back into the heap with an effective height of max(currentHeight, neighborHeight). This simulates raising the water level as the basin fills.
The key insight: the lowest boundary always determines the maximum water level of the region it expands into. Using a heap ensures cells are processed in increasing height order. Each cell is visited once and inserted into the heap at most once, giving O(mn log(mn)) time due to heap operations and O(mn) space for the visited matrix and heap. This approach combines ideas from Heap (Priority Queue), Breadth-First Search, and grid traversal.
Approach 2: Flood Fill Simulation (O(mn log(mn)) time, O(mn) space)
Another perspective treats the problem as a flood-fill from the outer boundary. Initialize the boundary as the starting frontier and gradually propagate inward. Instead of thinking about trapping water locally, maintain the current water level defined by the smallest boundary cell encountered. Each step expands to neighboring cells and updates the water level accordingly. If a cell is lower than the active water level, the difference contributes to trapped volume.
The flood fill behaves similarly to a Dijkstra-style expansion across the grid. The frontier must still be processed in increasing elevation order, so a priority queue is typically used internally. The algorithm marks cells as visited to prevent revisiting and keeps updating the effective boundary height as it expands inward. Complexity remains O(mn log(mn)) time with O(mn) auxiliary space.
This formulation helps when reasoning about water propagation in a matrix environment. It also clarifies why the outer boundary must be processed first: water can always escape through the lowest surrounding wall.
Recommended for interviews: The min-heap boundary expansion approach is what interviewers expect. It demonstrates understanding of priority queues, BFS-style grid traversal, and the key insight that the minimum boundary controls the water level. Explaining the flood-fill intuition helps justify the algorithm, but implementing the heap-based BFS shows stronger problem-solving skill.
This approach utilizes a min-heap (priority queue) to efficiently determine the minimum boundary height around a smaller section of the map. Initially, all the border points are pushed into the heap. We then process each cell in the heap by examining its neighbors. If the height of a neighboring cell is lower, it indicates that water can be trapped above it. The heap is utilized to ensure that the next cell to process is the one which determines the lowest possible trapped water boundary for its neighbors.
The function first initializes a priority queue with all boundary cells, marking them as visited. Cells are processed from the queue in order of increasing height. For each cell, its neighbors are checked to determine if water can be trapped. If so, water is added, and the neighbor cell is pushed into the queue as potentially trapping more water.
Python
Java
C++
JavaScript
C#
Time Complexity: O(m * n * log(m * n)), where m is the number of rows and n is the number of columns, due to priority queue operations.
Space Complexity: O(m * n) because of the auxiliary structures used for visited tracking and min-heap storage.
This approach employs a flood-fill technique starting from the boundary cells and leverages depth-first or breadth-first search to explore the inward cells. The idea is similar to how flood-fill works in graphics, where all connected cells are considered to be part of the same region and receive the same 'flood' level. This approach ensures that all accessible cells connected through any boundary are given a chance to receive water, effectively checking for possible traps.
This solution uses a BFS queue to perform the flood-fill operation on the height map. Each cell on the border is considered starting point, and its height is used to fill inward cells until no more water can be trapped. The design tracks visited cells and updates levels using the fill technique to maintain overflow boundaries.
Python
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, given the potential need to inspect each cell.
Space Complexity: O(m * n) to handle the visited array and BFS queue.
| Approach | Complexity |
|---|---|
| Using a Min-Heap Priority Queue | Time Complexity: O(m * n * log(m * n)), where m is the number of rows and n is the number of columns, due to priority queue operations. |
| Flood Fill Technique | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, given the potential need to inspect each cell. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap Priority Queue + BFS | O(mn log(mn)) | O(mn) | Standard optimal solution for 2D trapping rainwater problems. Expected in interviews. |
| Flood Fill Boundary Expansion | O(mn log(mn)) | O(mn) | Useful for reasoning about water propagation across a grid or explaining the heap solution. |
Trapping Rain Water II - Leetcode 407 - Python • NeetCodeIO • 29,023 views views
Watch 9 more video solutions →Practice Trapping Rain Water II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor