use min heap (priority queue) to process cells in order of height. start by adding all boundary cells to the heap. for each cell popped, check its neighbors: if neighbor is lower, it can trap water up to the current cell's height.
when processing a neighbor lower than current cell, add trapped water (current height - neighbor height) and push neighbor with current height (water level). if neighbor is higher, push it with its own height.
implementation details
- custom priority queue with min heap for cells
- start from all boundary cells (outer edges)
- process cells in height order (lowest first)
- track visited cells to avoid reprocessing
- water trapped = max(0, boundary_height - cell_height)
complexity
O(mn log(mn)) time for heap operations on all cells. O(mn) space for heap and visited array.