Given an non-negative integer array arr[] of length n representing the height of blocks.
If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season.
Example
Input: arr[] = {2, 1, 3, 0, 0, 2, 0}, n = 7, Output: 5
Solutions
Method 1: In O(n) time and O(n) space
A block represented by an element of the array can store water if there are higher bars on the left and the right.
Moreover, the amount of water to be stored on each block can be found by subtracting its height from the minimum of the highest bars on the left and right sides.
The idea is to iterate over the array twice, once to calculate for each element the highest bars on the left and a second time to calculate the highest bars on the left as well as the min of the two (highest bars on the left and right sides).
We can also calculate the amount of water to be stored on each block in the second loop, and if the result is positive, add it to the total water.
Complexity
The time complexity of this solution is O(n) and space complexity is O(n).