'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
Contributed by

## 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:
``````

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
``````
Console