Terrain Water Simulation

Terrain Water Simulation appears to be a specialized Airbnb interview problem involving a 2D height map (terrain array) where you simulate how water accumulates or flows based on gravity, using techniques like greedy algorithms for local minima filling or BFS for flood fill propagation.

Problem Statement

Given a 2D grid representing terrain heights, determine the amount of water that can be trapped in each cell after rain falls uniformly. Water flows downhill to lower adjacent cells (up, down, left, right) but gets trapped in depressions bounded by higher terrain. Solve using greedy (prioritize lowest boundaries) or BFS (from edges inward) to compute trapped water per cell.[1][5]

Key Variants

• Trapping Rain Water 2D: Extension of 1D problem; start from boundary cells (which hold no water) and use priority queue (greedy, min-heap by height) or BFS levels to "flood fill" inward, tracking max boundary height.[5]
• Simulation Flow: For dynamic flow, model water heights evolving over terrain, preventing overflow via neighbor comparisons (greedy local redistribution) or BFS shortest path to outlets.

Input/Output Examples

Example 1 (standard 2D trapping): Input: heights = [[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: [[0,0,0,0,0],[0,1,2,1,0],[0,1,3,1,0],[0,1,2,1,0],[0,0,0,0,0]] (water depths; total 10 units).[5]

Example 2 (no trapping): Input: [[2,1],[4,4]] Output: [[0,0],[0,0]] (water flows off edges).[5]

Constraints

• 1 ≤ m, n ≤ 300 (grid rows/columns).
• 0 ≤ heights[i][j] ≤ 10^4.
• Time: O(mn log(mn)) acceptable for greedy heap; O(mn) for BFS.
• Space: O(mn).[5]