Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For the input array [2, 0, 2], we can trap 2 units of water.
| _ |
For the input array [3, 0, 0, 2, 0, 4].
| | |
|_ _| _ |
we can trap 10 units of water.
First let's try to simplify the problem.
An element will only be able to store water if there are bars of higher height to the left and right of it.
A naive approach would be to traverse the array for each element finding the elements with the highest high on the left and right.
We can then take the minimum of the two values and get the value of water stored at that element.
Time complexity of this solution is O(N^2)
A more efficient approach would be to compute the highest element on the left for all the elements and the highest element on the right for all the elements and store them.
This will bring down the complexity to O(N).
The above approach can be implemented as follows: