[PYTHON] [Competition Pro] How much water does this mountain collect? (2D, 3D)

Suddenly, how much water do you think this mountain will collect?

If it rains from above, you should probably have a pond like this.

If this mountain is placed in a coordinate system with 1 square in the vertical and horizontal directions, the amount of water that collects will be 6. If this mountain becomes huge, how can we find the amount of water?

What about a mountain that looks three-dimensional like this? Do you care about the amount of water that collects?

Regardless of how much you sympathize with it, this problem is actually a well-known problem that appears in coding interview textbooks. The solution was interesting, so I would like to introduce it.

Two-dimensional mountain

First, consider the case where the mountain has a direction and a height in two dimensions. Expressing the height of the mountain as an array, the problem is that the array that represents the height of each point $ height = [0,1,0,2,1,0,1,3,2,1,2,1 You can think of it as a problem of designing a function that takes $ as an input and returns the amount of accumulated water.

def trap_water(height: List[int]) -> int:
  ...
  return capacity

Solution 1

The first time you see this problem, it may not be easy to come up with how to calculate the amount of water. However, we notice that there is a certain amount of water that accumulates at each $ x $ coordinate. If you look at both sides of a certain point and there are points higher than your current location on both sides, water will accumulate to the lower height of them. For example, if you look at the point of $ x = 4 $ in the first figure, $ x = 2 $ is the highest at height 2 on the right side, and $ x = 6 $ is the highest at height 3 on the left side. Since $ x = 4 $ is 0 in height, we know that water collects $ 2-0 = 2 $.

More generalized, the water that collects at the $ x = i $ point can be written as:

water[i] = \max(0, \min(\max(height[:i]),\max(height[i+1:])) - height[i]))

If you put this into the code, it will be as follows.

def trap_water(height: List[int]) -> int:
  if not height:
    return 0
        
  n = len(height)
  capacity = 0
  for i in range(n):
    left_max = max(height[:i]) if i > 0 else 0
    right_max = max(height[i+1:]) if i < n-1 else 0
            
  capacity += max(0, min(left_max, right_max) - height[i])
            
  return capacity

Since this calculates the right side and left side for each x coordinate, the time complexity is $ O (n ^ 2) $. On the other hand, the amount of spatial complexity is $ O (1) $.

Solution 2

Basically, there is a desire to make the solution of $ O (n ^ 2) $ faster. Solution 1 calculated the highest points on both sides for each $ x $ coordinate, but the calculation at $ x = i $ and the calculation at $ x = i + 1 $ are almost the same. .. Specifically, the highest point on the left side of $ x = i $ is higher than the highest point on the left side of $ x = i-1 $ compared to the height of $ x = i $. It is useless to calculate this from the beginning every time, so the idea is to save the value.

First, create an array $ left \ _max $ that stores the highest point on the left side of the $ x = i $ point. $ left \ _ max [i] $ stores the values ​​for each of $ x = 1, ..., i $. The following relationship holds for $ left \ _ max $.

left\_max[i] = max(left\_max[i-1], height[i])

Similarly, the array $ right \ _max $ that stores the highest point on the right side of the $ x = i $ point has the following relationship.

right\_max[i] = max(right\_max[i+1], height[i])

If you make this first, the amount of water that collects at $ x = i $ will be the same as in Solution 1.

water[i] = \max(0, \min(left\_max[i-1],right\_max[i+1]) - height[i]))

Can be written. The code for this looks like this:

def trap_water(height: List[int]) -> int:
  if not height:
    return 0
        
  n = len(height)
  capacity = 0
  left_max, right_max = [0]*n, [0]*n
  left_max[0], right_max[-1] = height[0], height[-1]
  for i in range(1,n):
    left_max[i] = max(left_max[i-1], height[i])
        
  for i in reversed(range(n-1)):
    right_max[i] = max(right_max[i+1], height[i])
            
  for i in range(1,n-1):
    capacity += max(0, min(left_max[i-1], right_max[i+1]) - height[i])
            
  return capacity

In this case, the time complexity is $ O (n) $ because the operation of viewing the array in order is performed only three times. The amount of spatial complexity is $ O (n) $ because it holds $ left \ _max $ and $ right \ _max $.

By calculating $ right \ _ max $ and $ water $ at the same time, the order does not change, but the time complexity and spatial complexity can be reduced by one time.

def trap_water(height: List[int]) -> int:
  if not height:
    return 0
        
  n = len(height)
  capacity = 0
  left_max = [0]*n
  left_max[0] = height[0]
  for i in range(1,n):
    left_max[i] = max(left_max[i-1], height[i])
        
  right_max = height[-1]
  for i in reversed(range(1,n-1)):
    capacity += max(0, min(left_max[i-1], right_max) - height[i])
    right_max = max(right_max, height[i])            
            
  return capacity

Solution 3

Most people will be satisfied if the time complexity and space complexity are $ O (n) $. However, in fact, this method can be further improved.

In solutions 1 and 2, it was found that the amount of water accumulated is determined by the heights on both sides of the $ x = i $ point, but more specifically, the amount of water accumulated is determined by the lower height of both sides. Therefore, this method is to count the height from both sides at the same time and discover it.

Place pointers on both sides of the mountain. In other words, put the pointer $ pl $ at $ x = 0 $ and $ pr $ at $ x = n-1 $. Then, according to the procedure, move $ pl $ to the right and $ pr $ to the left. In addition, record the value $ max \ _height $ as the highest point you have ever seen. Initialize this to 0 at first.

The problem is how to move the pointer. First, compare $ height [pl] $ and $ height [pr] $, that is, the height at the pointer point. Then, perform the following two operations for the smaller one.

-Compare $ max \ _height $ with $ height [p] $ at the pointer point -If $ max \ _height $ is larger, the amount of water that collects at point p will be $ max \ _ height --height [p] $. -If $ height [p] $ is larger, water will not collect. Update $ max \ _height $ to $ height [p] $. --Advance the pointer one step forward.

In addition, $ pl $ and $ pr $ are collectively written as $ p $. Continue this as long as $ pl $ <$ pr $.

So what the hell is this doing? As you can see by actually moving it according to the procedure, $ x <= pl $ and $ pr <= x $, that is, the highest point outside the two pointers is higher than $ max \ _height $, and You can see that one of them is exactly the same as $ max \ _height $. For example, if you move the pointer $ pl $

--If $ height [pl]> = max \ _height $, water will not collect -If $ height [pl] <max \ _height $, there is a point of height $ max \ _height $ in the area of ​​$ x <pl $, and height $ in the area of ​​$ pr <= x $. There is a point above max \ _height $

Is established. So, inevitably, the amount of water that collects is $ max (max \ _ height --height [p], 0) $.

If you move it up to the 9th step in order, it will be as shown in the figure below. Can you get an image somehow ...? When $ height [pl] = height [pr] $, $ pr $ is moved, but it doesn't matter which one. Eventually, $ pl $ and $ pr $ will gather at the highest point in the whole.

The code is as follows.

def trap_water(height: List[int]) -> int:
  if not height:
    return 0
    
  left, right = 0, len(height)-1
  max_val = capacity = 0
  while left < right:
    if height[left] <= height[right]:
      cur_val = height[left]
      left += 1
    else:
      cur_val = height[right]
      right -= 1
                
    capacity += max(0, max_val - cur_val)
    max_val = max(max_val, cur_val)
            
  return capacity

In this case, the time complexity remains $ O (n) $, but the spatial complexity could be $ O (1) $ because it is no longer necessary to hold the highest point.

3D mountain

Next, let us consider the case where the mountain is three-dimensional. A three-dimensional mountain looks like this (I'm sorry for the rattling because it's handwritten).

In this case, the input will be an array like the one below.

\begin{align}
height = [&[1,4,3,1,3,2],\\
          &[3,2,1,3,2,4],\\
          &[2,3,3,2,3,1]]
\end{align}

If you think about it for a moment, you can see that this is considerably more complicated than a two-dimensional mountain. In the case of two dimensions, it was good to consider the heights on both sides, but we have to consider the flow of water in various directions. Even if people think that it is a big mountain, it is likely to make a mistake.

solution

This problem can be solved by applying Solution 3 in the case of two dimensions. In Solution 3, in the case of 2D, two pointers were prepared at both ends and the smaller one was moved inward.

--Place the pointer on the outermost position to start --Select the smallest pointer and perform operations such as calculating the amount of water for that position. --Move the pointer from that position to a place where you can move

It can be rephrased as performing the operation. According to this, it extends to 3D operation. In other words

  1. Place the pointer over the entire circumference of the starting plane
  2. Choose the lowest height point from them
  3. Find the height of the water at that point
  4. Update $ max \ _height $
  5. Place the pointer in a position that is reachable from that position and has not yet been placed.
  6. Repeat steps 2 to 5 until there are no more pointers

Is to be. If you repeat this operation, it will be as below.

As you can see, there are always "reached" blocks on the plane, which are the walls of $ max \ _height $ and above. Therefore, the height of water can be calculated by $ \ max (max \ _height-height [p], 0) $.

Now, the code that realizes this is a heap (priority queue) because there are operations to retrieve the minimum value of the set and operations to add and delete elements to the set for the set of coordinates where the pointer is placed. Is the best. In the heap, you can add and remove elements with $ O (\ log n) $, and search for the minimum value with $ O (1) $.

def trap_water_3d(self, height: List[List[int]]) -> int:
  if not heightMap or not heightMap[0]:
    return 0
        
  h, w = len(heightMap), len(heightMap[0])
  if h <=2 or w<=2:
    return 0
        
  visited = [[False]*w for _ in range(h)]
  que = []
  for i in range(h):
    que.append((heightMap[i][0], i, 0))
    que.append((heightMap[i][w-1], i, w-1))
    visited[i][0] = visited[i][w-1] = True
  for j in range(w):
    que.append((heightMap[0][j], 0, j))
    que.append((heightMap[h-1][j], h-1, j))
    visited[0][j] = visited[h-1][j] = True
        
  heapq.heapify(que)
  max_val = capacity = 0
  while que:
    val, r, c = heapq.heappop(que)
    capacity += max(0, max_val - val)
    max_val = max(max_val, val)
    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
      if 0<=r+dr<h and 0<=c+dc<w and not visited[r+dr][c+dc]:
        visited[r+dr][c+dc] = True
        heapq.heappush(que, (heightMap[r+dr][c+dc], r+dr, c+dc))
                    
  return capacity

Here, first put the coordinates of the outer circumference and its height in $ que $. $ visited $ means the coordinates you have already visited. Take the smallest element from $ que $, add the amount of water at that point to $ capacity $, and update the height $ max \ _val $ at the highest point. Then, of the four points adjacent to the current coordinates, put the points that have not been visited yet in $ que $. You can scan all the squares by continuing this until $ que $ is empty. Regarding the time complexity, if the number of squares is $ n $, it will be $ O (n \ log n) $ because it will be added to and extracted from $ que $ at most once for each point. .. The amount of spatial complexity is $ O (n) $, which is the capacity of $ que $ that stores the coordinates.

Furthermore, by applying this idea, it should be possible to find the amount of water that accumulates in higher-dimensional mountains. For an n-dimensional matrix containing the height of each point, the outer circumference should be the starting point and the heap should be used for scanning. If you read this article, you should already be looking for water that collects in a four-dimensional mountain **.

Summary

So far, we have calculated the amount of water that collects in the mountains. With this knowledge, please try to find out the amount of water that has accumulated in the mountains near you (?)

** Reference (from LetCode) ** Trapping Rain Water Trapping Rain Water II

Recommended Posts

[Competition Pro] How much water does this mountain collect? (2D, 3D)