Leetcode 42: Trapping Rain Water

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 the solution:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *