Trapping Rain Water II - Video Solutions

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.