LeetCode, 𝐃𝐚𝐲-19/365-DSA-Coding 𝐉𝐨𝐮𝐫𝐧𝐞𝐲…Google Prep…

Aaqib Ali
3 min readJan 19, 2025

--

Today I Learned This Problem: 407. Trapping Rain Water II

Problem Overview:

The problem asks us to calculate the amount of water trapped after rainfall in a 3D grid represented as a height map. The height map is given as a 2D matrix, where each cell represents the height of the terrain. Our goal is to find the total volume of water that can be trapped between the terrain blocks.

This problem introduces concepts of priority queues, BFS, and dynamic boundary management, making it a great practice for grid traversal and algorithm optimization.

Challenges Involved:

  1. Boundary Management:
  • Understanding how water can flow from higher boundaries to lower cells and how to handle dynamic updates to the boundary.

2. Heap Utilization:

  • Using a min-heap to always process the lowest boundary cell, ensuring that trapped water calculations are accurate.

3. Efficient Traversal:

  • Avoiding redundant visits to already-processed cells while ensuring all potential cells are evaluated for water trapping.

Explanation:

To solve the problem, we use the min-heap to simulate water flow and keep track of the terrain’s boundaries. Here’s the step-by-step breakdown:

  1. Add Boundary Cells:
  • Initialize the heap with all boundary cells of the height map.
  • Mark them as visited since no water can flow outside the boundary.
  1. Simulate Water Flow:
  • Process cells in the heap by always taking the one with the lowest height.
  • Check its neighbors. If a neighbor is unvisited, calculate the trapped water as the difference between the current cell’s height and the neighbor’s height (if positive).
  1. Update Boundary:
  • Push the neighbor cell into the heap with its new height, which is the maximum of its original height and the current cell’s height.
  1. Repeat Until Complete:
  • Continue processing until all reachable cells have been evaluated.

My Solution Approach:

Initialization:

  • Create a visited matrix to keep track of processed cells.
  • Add all boundary cells to a minHeap.

Iterate Through Cells:

  • Use BFS with the heap to simulate water flow, calculate trapped water for neighbors, and update boundaries dynamically.

Final Calculation:

  • The cumulative water trapped is updated as we process neighbors.

Python Code:

import heapq

class Solution:
def trapRainWater(self, heightMap):
if not heightMap or not heightMap[0]:
return 0

m, n = len(heightMap), len(heightMap[0])
visited = [[False] * n for _ in range(m)]
minHeap = []

# Add boundary cells to the heap
for i in range(m):
for j in (0, n - 1):
heapq.heappush(minHeap, (heightMap[i][j], i, j))
visited[i][j] = True
for j in range(n):
for i in (0, m - 1):
if not visited[i][j]:
heapq.heappush(minHeap, (heightMap[i][j], i, j))
visited[i][j] = True

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
waterTrapped = 0

# Process cells in the minHeap
while minHeap:
height, x, y = heapq.heappop(minHeap)

for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
waterTrapped += max(0, height - heightMap[nx][ny])
heapq.heappush(minHeap, (max(height, heightMap[nx][ny]), nx, ny))
visited[nx][ny] = True

return waterTrapped

Other Possible Solutions:

  • DFS Approach: While possible, it is less efficient as DFS does not dynamically update the boundary heights, leading to redundant calculations.
  • Brute Force: Iterating through all cells repeatedly to calculate water trapping is computationally expensive and impractical for large grids.

Learnings:

  1. Heap Optimization: Min-heaps are ideal for problems requiring dynamic boundary management.
  2. BFS Traversal: Effective for grid-based problems with neighbor relationships.
  3. Dynamic Programming Insights: Updating boundaries dynamically helps achieve optimal solutions.

Real-Life Usage:

  1. Flood Simulation: Predict areas of water accumulation based on terrain height maps.
  2. 3D Modeling: Simulating water flow and volume in game development or virtual environments.

To sum up…

Thank you for reading! If this explanation clarifies the problem for you, feel free to share your thoughts or suggest alternative solutions. Keep learning, coding, sharing, and growing!

--

--

No responses yet