Trapping Rain Water II - Solution & Explanation
Problem Statement
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 * 104
Approach Overview
Problem 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.
Approach 1: Using a Min-Heap Priority Queue
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.
Code
Python
Java
C++
JavaScript
C#
Complexity
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.
Approach 2: Flood Fill Technique
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.
Code
Python
Complexity
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 3: Priority Queue (Min Heap)
This is a variant of the trapping rain water problem. Since the heights on the matrix boundaries are fixed, we can add these boundary heights to a priority queue. Then, we repeatedly take out the minimum height from the priority queue and compare it with the heights of its four adjacent cells. If an adjacent cell's height is less than the current height, we can trap water there. The volume of trapped water is the difference between the current height and the adjacent height. We then add the larger height back to the priority queue and repeat this process until the priority queue is empty.
The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n), where m and n are the number of rows and columns in the matrix, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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. |
| Priority Queue (Min Heap) | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Trapping Rain Water II - Leetcode 407 - Python • NeetCodeIO • 30,521 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Trapping Rain Water II easy or hard?
How to solve Trapping Rain Water II in O(n)?
What is the best approach for Trapping Rain Water II?
What data structure is used in Trapping Rain Water II?
What is the time complexity of Trapping Rain Water II?
Trapping Rain Water II Python or Java solution approach?
Is Trapping Rain Water II asked at Google or Amazon interviews?
Ready to solve this problem?
Practice Trapping Rain Water II with our built-in code editor and test cases.
Practice on FleetCode