Tilted Terrain Sum
February 10, 2024
Problem Statement #
You are given a 2D integer grid terrain
representing the elevation of a landscape. Imagine that rain falls uniformly across the area and is trapped depending on the terrain’s shape. Calculate the total volume of water that would be trapped.
Example:
Input: terrain =
[
[2, 3, 5, 1],
[6, 5, 3, 4],
[3, 1, 2, 5]
]
Output: 7
Solution Approach #
This problem can be effectively solved using a combination of BreadthFirst Search (BFS) and a priority queue (MinHeap). The core idea is to start from the border cells of the terrain, which act as initial water sources, and gradually explore inwards while tracking water levels that can be trapped.
Algorithm:

Initialization:
 Create a priority queue/minheap
heap
to store cells and their corresponding potential water levels.  Create a boolean
visited
matrix to keep track of processed cells.  Add all border cells of the
terrain
into theheap
. The potential water level at the border is the cell’s height itself.
 Create a priority queue/minheap

BFS with Heap:
 While the
heap
is not empty: Dequeue the cell (
row
,col
,height
) with the minimumheight
from theheap
.  If the cell is already
visited
, continue to the next iteration.  Mark the cell as
visited
.  For each unvisited neighbor (
newRow
,newCol
) of the current cell: Calculate the maximum water level that can be trapped at the neighbor:
maxWaterLevel = max(height, terrain[newRow][newCol])
 If
maxWaterLevel
is greater than the neighbor’s original height, the difference represents trapped water:waterTrapped = maxWaterLevel  terrain[newRow][newCol]
Updateterrain[newRow][newCol]
tomaxWaterLevel
(effectively raising the ground level).  Add the neighbor to the
heap
with its associatedmaxWaterLevel
.
 Calculate the maximum water level that can be trapped at the neighbor:
 Dequeue the cell (
 While the

Calculate Total Trapped Water:
 Iterate through the
terrain
grid.  For each cell, if the current cell’s height is less than the final height in the
terrain
grid, the difference represents trapped water. Accumulate this difference into atotalWater
variable.
 Iterate through the
Code (Python):
import heapq
def trappedWater(terrain):
rows = len(terrain)
cols = len(terrain[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
heap = []
# Add border cells to heap
for i in range(rows):
for j in range(cols):
if i == 0 or i == rows  1 or j == 0 or j == cols  1:
heapq.heappush(heap, (terrain[i][j], i, j))
visited[i][j] = True
totalWater = 0
directions = [(1, 0), (1, 0), (0, 1), (0, 1)]
while heap:
height, row, col = heapq.heappop(heap)
for dx, dy in directions:
newRow, newCol = row + dx, col + dy
if 0 <= newRow < rows and 0 <= newCol < cols and not visited[newRow][newCol]:
maxWaterLevel = max(height, terrain[newRow][newCol])
if maxWaterLevel > terrain[newRow][newCol]:
totalWater += maxWaterLevel  terrain[newRow][newCol]
heapq.heappush(heap, (maxWaterLevel, newRow, newCol))
visited[newRow][newCol] = True
return totalWater