Calculate the amount of water a tool described by an array can contain

Question

There is a tool for collecting rainwater. The transect chart of the tool is described by an array in the length of n.

For example: for this array {2,1,1,4,1,1,2,3} the transect chart is:

I am required to calculate the amount of water the tool can sustain, in time and place complexity of O(n). . For the array above it is 7 (the grey area).

My thought:

Since it's a graphical problem, my initial thought was to first calculate the maximum of the array and multiply it by n. This is the starting volume I need to subtract from.

For example in the array above I need to subtract the green area and the heights themselves:

This is where I'm stuck and need help in order to do so in the required complexity.

Note: Maybe I'm overthinking and there are better ways to handle this problem. But as I said, since it's a graphical problem, my first thought was to go for a geometric solution.

Any tips or hints would be appreciate.

Answer 1

The water level at position i is the smaller of:

• The maximum container height at positions <= i; and
• The maximum container height at positions >= i

Calculate these two maximum values for every position using two passes through the array, and then sum up the differences between the water levels and the container heights.