This is a tricky leetcode problem. There are a few observations that need to be made. Water traps between two bars and only fills each of those gaps to a volume that is the gap’s height taken away from the smaller of the two enclosing bars’ height. It is easier to calculate if the two enclosing bars are ascending, in which case we just compare each gap’s height to the first bar’s height. Descending is more tricky as we need to look ahead to find the next tallest bar and that requires an extra array pass, which would result in O(n²). We can use a two pointer (left and right) technique to ensure that we are always solving ascending bounding bars. We just iterate the pointer that has the smallest enclosing bar (max height bar). Here are my whiteboard notes, which might make it clearer:
And here are is my c++ source code for this 2 pointer solution:
Here is an alternative solution that uses 2 passes. The first pass looks for ascending bars, keeping track of the maximum bar and previous maximum. When it finds a new maximum, it then calculates the area between this maximum and the previous maximum by iterating backwards. After this forward pass we then do a reverse pass, looking for ascending bars from back to front. There is one tricky edge case, which is two bars that are equal size and are bigger than the rest of the bars. I have a check for this in the second loop, which skips the calculation.
Source code for the 2 pass solution:
https://gist.github.com/adamkorg/142f8a73d8db07eec43117a0842e9541