Trapping Rain Water II

The problem requires finding the volume of water that can be trapped on a 2D elevation map. We can approach it by using a Priority Queue.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from queue import PriorityQueue

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

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

        # Push all boundary cells to the priority queue
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0 or i == m - 1 or j == n - 1:
                    pq.put((heightMap[i][j], i, j))
                    visited[i][j] = True

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

        while not pq.empty():
            height, x, y = pq.get()

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

        return result

This code will calculate the trapped rainwater volume based on the given heightMap. It starts by adding the boundary cells to a priority queue and then iteratively processes cells from the queue, updating the water volume based on the heights of the neighboring cells. It ensures that the processed cells are marked as visited to avoid double counting.

Identifying Problem Isomorphism

“Trapping Rain Water II” is approximately isomorphic to “Swim in Rising Water”.

In “Trapping Rain Water II”, you have a 2D grid representing an elevation map where the value at each point is the height above sea level. Rain starts to fall, and you need to calculate how much rainwater can be trapped in the grid.

In “Swim in Rising Water”, you also have a 2D grid representing an elevation map. The water starts to rise from level 0, and you need to find the minimum time to swim to the other end of the grid.

Both involve a 2D grid and an incrementally increasing water level, and the tasks relate to how the water interacts with the landscape’s elevation. The key difference is in the tasks: in “Trapping Rain Water II”, you calculate the trapped rainwater, while in “Swim in Rising Water”, you calculate the minimum time to swim to the other end of the grid.

“Swim in Rising Water” is simpler because it requires finding a path through the grid with a monotonic function (minimum time), while “Trapping Rain Water II” requires calculating the volumetric capacity of the landscape, which is more complex.

10 Prerequisite LeetCode Problems

“Trapping Rain Water II” requires understanding of data structures such as priority queues, and the ability to visualize and traverse in three dimensions. Here are 10 problems to prepare:

  1. “Trapping Rain Water” (LeetCode Problem #42): This problem is a simpler version that only involves trapping rain water in one dimension.

  2. “Binary Heap Operations” (LeetCode Problem #1405): This problem gives a basic understanding of how a priority queue (heap) operates, which is necessary for the “Trapping Rain Water II” problem.

  3. “Heap Implementation” (LeetCode Problem #1439): This is another heap related problem which helps in understanding priority queues.

  4. “Kth Largest Element in an Array” (LeetCode Problem #215): This problem requires the use of a priority queue to solve it and provides practice on the application of this data structure.

  5. “Top K Frequent Elements” (LeetCode Problem #347): This is a bit more complex heap related problem and provides a nice practice to understand priority queues.

  6. “Merge k Sorted Lists” (LeetCode Problem #23): This problem also requires the use of a priority queue and helps you understand how to use it in a more complex scenario.

  7. “Flood Fill” (LeetCode Problem #733): This problem helps you to understand the concept of flooding an area, which is applicable in the “Trapping Rain Water II” problem.

  8. “01 Matrix” (LeetCode Problem #542): This problem requires multi-directional traversal, much like “Trapping Rain Water II”.

  9. “Rotting Oranges” (LeetCode Problem #994): This problem gives you practice on grid-based breadth-first search (BFS), which will be useful in “Trapping Rain Water II”.

  10. “Walls and Gates” (LeetCode Problem #286): This problem involves updating distances in a grid, which can be helpful to understand the multi-directional traversal required in “Trapping Rain Water II”.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

        m, n = len(heightMap), len(heightMap[0])
        if m < 3 or n < 3:
            return 0

        heap = []
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    heapq.heappush(heap, (heightMap[i][j], i, j))
                    heightMap[i][j] = -1

        level, res = 0, 0

		while heap:
            height, x, y = heapq.heappop(heap)
            level = max(height, level)

            for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= i < m and 0 <= j < n and heightMap[i][j] != -1:
                    heapq.heappush(heap, (heightMap[i][j], i, j))

                    if heightMap[i][j] < level:
                        res += level - heightMap[i][j]

                    heightMap[i][j] = -1

        return res

Problem Classification

Trapping Rain Water II - The problem asks to compute the volume of water trapped on a 3D terrain. This is a Volume Calculation Problem.

Language Agnostic Coding Drills

  1. Array Manipulation: Learn how to create, access, and manipulate arrays. This is an important skill since the heightMap variable is a 2-dimensional array.

  2. Conditional Statements: Master the use of if statements to control the flow of a program. Here, it’s used to check for edge cases and control program flow.

  3. Loops: Understand how to use for loops to iterate over data structures. This code includes a nested for loop to iterate over the elements in heightMap.

  4. Heap Data Structure: Familiarize yourself with heap data structures and the Python heapq module. In this code, the heap is used to store the boundary elements of heightMap and to maintain a min-heap data structure for efficient retrieval of the smallest element.

  5. Tuple Data Structure: Learn how to create and manipulate tuples. Here, each element in the heap is a tuple of (height, x coordinate, y coordinate).

  6. 2D Array Edge Cases: Understand the edge cases when working with 2-dimensional arrays. This problem involves the boundaries of the heightMap, hence, it’s important to understand how to check if a given coordinate (i, j) is within the boundaries of the heightMap.

The problem-solving approach for this problem can be described as follows:

  1. Handle edge cases: If the heightMap is empty or has less than 3 rows or columns, it cannot trap any rainwater, so return 0.

  2. Initialize a heap with all the boundary cells of heightMap.

  3. Pop elements (cells) from the heap in increasing order of their height. For each cell, check its neighbours. If a neighbour cell’s height is less than the current water level, it can trap rainwater and add the volume to the result.

  4. Mark visited cells to avoid revisiting them.

  5. Push unvisited neighbour cells into the heap.

  6. Repeat steps 3-5 until the heap is empty. Return the total volume of trapped rainwater.

This solution uses a priority queue (heap) to perform a breadth-first search (BFS) from the outside inwards, always processing the cells with the lowest height first.

Targeted Drills in Python

Here are coding drills for each concept involved in the solution. Note that these are the building blocks for the final problem’s solution.

1. Array Manipulation

In Python, you can manipulate lists, which are equivalent to arrays in other languages.

1
2
3
4
5

# Create a 2D array (list of lists)
array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# Access elements
print(array[0][1])  # Output: 2

2. Conditional Statements

Python supports the usual logical conditions known from mathematics. These can be used in several ways, most commonly in “if statements”.

1
2
3
4
5
6
7
8
9

# Using if, elif (else if), else
a = 200
b = 33
if b > a:
  print("b is greater than a")
elif a == b:
  print("a and b are equal")
else:
  print("a is greater than b")

3. Loops

In Python, for and while loops are commonly used.

1
2
3
4
5
6
7
8

# A simple for loop
for i in range(5):
    print(i)

# A nested for loop
for i in range(3):
    for j in range(3):
        print(i, j)

4. Heap Data Structure

Python provides a module named heapq for efficient implementation of heap data structures.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import heapq

# Create a heap
heap = []
heapq.heappush(heap, (1, 'one'))
heapq.heappush(heap, (10, 'ten'))
heapq.heappush(heap, (5,'five'))

for x in heap:
	print(x)

5. Tuple Data Structure

A tuple is a collection which is ordered and unchangeable. Tuples are written with round brackets.

1
2
3
4
5

# Create a tuple
my_tuple = (1, "Hello", 3.4)

# Access tuple items
print(my_tuple[1])  # Output: "Hello"

6. 2D Array Edge Cases

When dealing with 2-dimensional arrays, it’s important to make sure any indices used are valid.

1
2
3
4
5
6
7
8
9

array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
m, n = len(array), len(array[0])

# Check if an index is valid
i, j = 4, 5
if 0 <= i < m and 0 <= j < n:
    print("Valid index")
else:
    print("Invalid index")

By understanding and practicing these smaller concepts, you can build up to understanding and solving the final problem of trapping rainwater.