Related Tags

python
javascript
c++
trapping rainwater

# The trapping rainwater algorithm in C++, Python, and Java. Educative Answers Team

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]

## The trapping rainwater problem

Given an elevation map, find the maximum amount of water that can be stored within the map (assuming infinite rainfall). Units of water trapped: 22

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​. Water above X = 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($n^2$) worst-case time complexity.

A better approach would be to:

• Traverse through the list once.
• Calculate the left_max for 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 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))

RELATED TAGS

python
javascript
c++
trapping rainwater 