Categories
interview

Maximum Water Capacity in a Histogram

bar graph

Calculate the maximum amount of water that can held within a bar graph without overflow.
The amount of water that can be held at any point is the difference of the minimum of the maximum of left bars and maximum of right bars and the height of that point.
If we don’t precompute the maximum values on left and right for every index, the time complexity becomes O(n^2). So we go with the precompute option.

Time Complexity O(n)
Space Complexity O(n)

Code

Output