Tilted Terrain Sum

Tilted Terrain Sum

February 10, 2024
medium
BFS, heap

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 Breadth-First Search (BFS) and a priority queue (Min-Heap). 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:

  1. Initialization:

    • Create a priority queue/min-heap 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 the heap. The potential water level at the border is the cell’s height itself.

  2. BFS with Heap:

    • While the heap is not empty:
      • Dequeue the cell (row, col, height) with the minimum height from the heap.
      • 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]
          Update terrain[newRow][newCol] to maxWaterLevel (effectively raising the ground level).
        • Add the neighbor to the heap with its associated maxWaterLevel.

  3. 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 a totalWater variable.

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