The trapping rainwater algorithm in C++, Python, and Java.
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:
![Elevation map: [1, 2, 1, 3, 1, 2, 1, 4, 1, 0, 0, 2, 1, 4]](/api/edpresso/shot/5552937621258240/image/5746657993949184)
The trapping rainwater problem
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.
Algorithm designing
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(right_max, left_max) is 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 left_max and right_max. However, it’s very obvious that the algorithm runs in the O() worst-case time complexity.
A better approach would be to:
- Traverse through the list once.
- Calculate the
left_maxfor each point and save it in a list. - Traverse again to do the same with
right_max. - Traverse once more to use this data and find the amount of water above each point.
This would have an O(n) time complexity.
Code
#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 mapn = len(elevation_map) #number of points on the map#lists to store the left_max and right_max of each point in the mapleft_max = [0]*nright_max = [0]*n#default valuesleft_max[0] = elevation_map[0]right_max[n-1] = elevation_map[n-1]#filling the left_max listfor i in range(1,n):left_max[i] = max(left_max[i-1], elevation_map[i])#filling the right_max listfor i in range(n-2, -1, -1):right_max[i] = max(right_max[i+1], elevation_map[i])#calculating the amount of waterfor i in range(n):water += min(left_max[i],right_max[i]) - elevation_map[i]return waterelevation_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))
Free Resources
