Today’s problem

https://leetcode.com/problems/trapping-rain-water-ii/description/

Intuition

In yesterday’s problem, we talked about the situation when we may consider using graph based methods to solve problems.

Now we can apply that criteria to this question: in this question, we found that the water can flow from four dirctions, which means that there are aftereffects.

Therefore, we need to apply graph based methods.

For each block, how many water it can store depends on the height difference between it and its lowest neighbor (image a wood bucket with edge heights you may see in psychology classes).

To clearify, here, water wall can also be s type of wall that contributes to the height.

To know the height of the walls, we first need to genereate a wall. But where is it?

The first wall you may consider is the outmost edge of the graph (such as the one shown in case two where stores water using the outmost edge).

Then we can find the lowest place on the wall to create more walls inside. That is, if its neighbor is higher than the point on the wall, then the point inside will become a new componenet of the wall. Otherwise, that inside point can store enough water to create a water wall as high as the current point.

Because we are using the lowest place on the wall, so all other parts of the wall would be higher or equal to the point, which means that the height of the wall is the upper bond of how many water can be stored inside the wall.

Approach

In this case, we can use a priority queue to find the point of the wall efficiently.

Then follow the algorithm described above:

1. Create the initial wall

2. loop:

   1. find the lowest point on the wall

   2. create new walls or new water walls

3. end loop

4. sum up all addition height of water walls

Complexity

• Time complexity: $O(NM\times log(NM))$

• Space complexity: $O(NM)$

Code

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        if len(heightMap) < 3 or len(heightMap[0]) < 3:
            return 0
        
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        vis = []
        n, m = len(heightMap), len(heightMap[0])
        q = []
        for i in range(n):
            heappush(q, (heightMap[i][0], i, 0))
            heappush(q, (heightMap[i][-1], i, m - 1))
            vis.append((i, 0))
            vis.append((i, m-1))
        for i in range(1, m - 1):
            heappush(q, (heightMap[0][i], 0, i))
            heappush(q, (heightMap[-1][i], n - 1, i))
            vis.append((0, i))
            vis.append((n-1, i))
        
        vis = set(vis)
        ans = 0

        while len(q) > 0:
            h, x, y = heappop(q)
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= m or (nx,ny) in vis:
                    continue
                if heightMap[nx][ny] < h:
                    ans += h - heightMap[nx][ny]
                heappush(q, (max(h, heightMap[nx][ny]), nx, ny))
                vis.add((nx, ny))
        return ans