Is Trapping Rain Water II easy or hard?

Trapping Rain Water II is classified as Hard on LeetCode. The difficulty comes from extending the 1D trapping rainwater concept into a 2D grid and recognizing that the solution requires a priority queue with BFS-style expansion.

How to solve Trapping Rain Water II in O(n)?

A true O(n) solution is not known for the 2D version of the problem. Unlike the 1D trapping rain water problem, the grid requires maintaining a global boundary order. The most efficient practical algorithm uses a min-heap and runs in O(mn log(mn)).

What is the best approach for Trapping Rain Water II?

The best approach uses a min-heap priority queue combined with BFS. All boundary cells are pushed into a heap, and the algorithm expands inward from the lowest boundary first. This ensures the current minimum wall height always determines how much water can be trapped. The time complexity is O(mn log(mn)) with O(mn) space.

What data structure is used in Trapping Rain Water II?

The core data structure is a min-heap (priority queue). It always processes the lowest boundary cell first, which determines the current water level. A visited matrix and BFS-style neighbor traversal are also used to explore the grid safely.

What is the time complexity of Trapping Rain Water II?

The optimal solution runs in O(mn log(mn)) time where m and n are grid dimensions. Each cell is processed once, but heap insertions and removals cost O(log(mn)). Space complexity is O(mn) for the visited matrix and priority queue.

Trapping Rain Water II Python or Java solution approach?

Python solutions typically use heapq with a visited matrix and directional traversal. Java implementations use PriorityQueue with a custom comparator for cell heights. Both follow the same boundary-expansion algorithm with O(mn log(mn)) complexity.

Is Trapping Rain Water II asked at Google or Amazon interviews?

Trapping Rain Water II appears in advanced interview rounds at companies like Google, Amazon, and Meta because it tests priority queues, BFS traversal, and spatial reasoning on grids. Candidates must combine multiple concepts rather than applying a single pattern.

Description Solution Video 15:19

407. Trapping Rain Water II

Hard64.0% acceptance14 companies

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.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 10⁴

Asked at 14 companies

Twitter Medianet Otterai Walmart Labs Flipkart Qualcomm Bytedance Samsung

Google Amazon Microsoft Meta

+2 more

Bloomberg Oracle

Topics

15:19

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

407. Trapping Rain Water II

Asked at 14 companies

Topics

Similar problems