Trapping Rain Water

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
193 upvotes
Asked in companies
OYOSalesforceAccenture

Problem statement

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.



Note : 
The width of each bar is the same and is equal to 1.
Example: 
Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Alt Text

Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
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 : 
Return an integer denoting the amount of water that can be trapped.
Sample Input 1:
4
2 1 1 4
Sample Output 1:
2
Explanation Of Sample Input 1:
Water trapped by:
     block of height 2 is 0 units.
     block of height 1 is 1 unit.
     block of height 1 is 3 1 unit. 
     block of height 4 is 3 0 units.

Hence the total is 2.
Sample Input 2:
5
8 1 8 2 4
Sample Output 2:
9
Explanation Of Sample Input 2:
Water trapped by:
     block of height 8 is 0 units.
     block of height 1 is 7 units.
     block of height 8 is 0 units. 
     block of height 2 is 2 units.
     block of height 4 is 0 units.

Hence the total is 9.
Expected Time Complexity:
The expected time complexity is O(n).
Constraints :
0 <= n <= 10^6
0 <= arr[i] <= 10^9

Time Limit: 1 sec
Hint

Figure a way to calculate the units of water that can be stored at every elevation in the map.

Approaches (3)
Brute Force Approach

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.
Time Complexity

O(n^2), Where ‘N’ is the total number of elevations in the map.

 

For every elevation we make ('n' - 1) operations to find the maximum height at the left and right. Hence, the overall space complexity will be O(n^2).

Space Complexity

O(1)

 

We are not using any extra space. Hence, the overall space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Trapping Rain Water
Full screen
Console