A site’s elevation map shows the different heights(elevations) at different points on a site. For the rainwater problem, the data is given in the form of a list.
We will use the example below throughout the shot:
Given an elevation map, find the maximum amount of water that can be stored within the map (assuming infinite rainfall).
The above diagram shows the water trapped after rainfall. Any more rainfall would result in an overflow. Thus, the amount of trapped water cannot increase.
Pause here, think of an algorithm that you can use to do this yourself.
Upon closer observation, it can be seen that the amount of water above a point (X) depends on the heights of the highest bars to the left and right of it, regardless of how far apart they are. Upon further exploration, it can be seen that the height of point X + the height of the water above it is equivalent to the minimum height of the highest bars around it.
Thus the height of the water, above a certain point, can be calculated using the formula:
water = minimum ( left_max, right_max ) - elevation_X
To see this in practice, refer to the diagram shown below. Here, the
left_max (3 units) is smaller than the
right_max (4 units), thus the minimum(
left_max (i.e., 3 units). The elevation at X itself is 2 units.
Hence, the water above X is 3 - 2 = 1 unit.
Now, we need to calculate the sum of the water above each point in the elevation map. This process can be made systematic in 2 ways.
The simplest algorithm would be to traverse through the list and, for every element, find its
right_max. However, it’s very obvious that the algorithm runs in the O() worst-case time complexity.
A better approach would be to:
left_maxfor each point and save it in a list.
This would have an O(n) time complexity.
#This method calculates the amount of water trapped. The only argument #passed is the elevation map, in form of a list. def trapped_water(elevation_map): water = 0 #keeps track of the total water as we traverse the elevation map n = len(elevation_map) #number of points on the map #lists to store the left_max and right_max of each point in the map left_max = *n right_max = *n #default values left_max = elevation_map right_max[n-1] = elevation_map[n-1] #filling the left_max list for i in range(1,n): left_max[i] = max(left_max[i-1], elevation_map[i]) #filling the right_max list for i in range(n-2, -1, -1): right_max[i] = max(right_max[i+1], elevation_map[i]) #calculating the amount of water for i in range(n): water += min(left_max[i],right_max[i]) - elevation_map[i] return water elevation_map = [1, 2, 1, 3, 1, 2, 1, 4, 1, 0, 0, 2, 1, 4] print("Total units of water trapped: ",trapped_water(elevation_map))
View all Courses