Trapping Rain Water

Posted: 31 Jul, 2020
Difficulty: Moderate


Try Problem

You have been given a long type array/list 'ARR' of size 'N'. It represents an elevation map wherein 'ARR[i]' denotes the elevation of the 'ith' bar. Print the total amount of rainwater that can be trapped in these elevations.

Note :
The width of each bar is the same and is equal to 1.
Input format :
The first line contains an integer 'T' which denotes the number of test cases. Then the test cases follow.

The first line of each test case contains an integer 'N' representing the size of the array/list.

The second line contains 'N' single space-separated integers representing the elevation of the bars.
Output Format :
For each test case, print in a single line a single integer denoting the total water that can be trapped.

The output of each test case will be printed in a separate line.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
0 <= N <= 10^4
0 <= ARR[i] <= 10^9

Time Limit : 1 sec
Approach 1

The idea here is to travel over every elevation on the map and calculate the units of water the elevation can store.


Here is the algorithm :


  1. Iterate over every elevation or element and find the maximum elevation on to the left and right of it. Say, the maximum elevation on to the left of the current elevation or element that we are looking at is ‘maxLeftHeight’ and the maximum elevation on to the right of it is ‘maxRightHeight’.
  2. Take the minimum of ‘maxLeftHeight’ and ‘maxRightHeight’ and subtract it from the current elevation or element. This will be the units of water that can be stored at this elevation.
  3. Compute units of water that every elevation can store and sum them up to return the total units of water that can be stored.
Try Problem