'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Trapping Rain Water

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
136 upvotes
Asked in companies
Paytm (One97 Communications Limited)AtlassianJP Morgan

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 )
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
Full screen
Console