Trusted answers to developer questions

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:

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(`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($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.

#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 = [0]*n right_max = [0]*n #default values left_max[0] = elevation_map[0] 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

Copyright ©2022 Educative, Inc. All rights reserved

RELATED COURSES

View all Courses

Keep Exploring

Related Courses