How do you solve Trapping Rain Water II on LeetCode?

Trapping Rain Water II (LeetCode #407) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n * log(m + n)) time complexity and O(m * n) space complexity. Key insight: Water can only be trapped in valleys surrounded by higher elevations.

What is the brute force solution for Trapping Rain Water II?

The brute force approach for Trapping Rain Water II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each cell in the height map to determine how much water can be trapped above it by looking at the maximum heights of the surrounding cells. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(m * n * log(m + n)).

What are the interview tips for Trapping Rain Water II?

Explain your thought process clearly as you code. Discuss edge cases, such as flat areas or single rows/columns. Practice visualizing the problem with diagrams or drawings.

What are common mistakes when solving Trapping Rain Water II?

Not considering the boundaries properly. Forgetting to mark cells as visited, leading to infinite loops.

#407

Trapping Rain Water II

Hard

ArrayBreadth-First SearchHeap (Priority Queue)MatrixHeapGraph (BFS)

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(m * n * log(m + n))
Space	O(1)	O(m * n)

💡

Intuition

Time O(m * n * log(m + n))Space O(m * n)

The optimal solution uses a priority queue (min-heap) to efficiently track the boundaries of the water trap. By processing the lowest boundary first, we can ensure that we calculate the water trapped correctly without missing any potential areas.

⚙️

Algorithm

3 steps

1Step 1: Initialize a min-heap and add all boundary cells to it, marking them as visited.
2Step 2: While the heap is not empty, extract the cell with the lowest height.
3Step 3: For each unvisited neighboring cell, calculate the water that can be trapped based on the current cell's height and add it to the total. Update the neighbor's height if necessary and add it to the heap.

solution.py33 lines

1# Full working Python code
2import heapq
3
4def trapRainWater(heightMap):
5    if not heightMap:
6        return 0
7    m, n = len(heightMap), len(heightMap[0])
8    visited = [[False] * n for _ in range(m)]
9    min_heap = []
10
11    for i in range(m):
12        for j in range(n):
13            if i == 0 or i == m-1 or j == 0 or j == n-1:
14                heapq.heappush(min_heap, (heightMap[i][j], i, j))
15                visited[i][j] = True
16
17    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
18    total_water = 0
19    max_height = 0
20
21    while min_heap:
22        height, x, y = heapq.heappop(min_heap)
23        max_height = max(max_height, height)
24        for dx, dy in directions:
25            nx, ny = x + dx, y + dy
26            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
27                visited[nx][ny] = True
28                total_water += max(0, max_height - heightMap[nx][ny])
29                heapq.heappush(min_heap, (heightMap[nx][ny], nx, ny))
30
31    return total_water
32
33print(trapRainWater([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]))

ℹ

Complexity note: The time complexity is O(m * n * log(m + n)) due to the priority queue operations, while the space complexity is O(m * n) because of the visited array and the heap.

1Water can only be trapped in valleys surrounded by higher elevations.
2The boundary cells determine the maximum height for water trapping.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.