Tuesday, October 25, 2011

Volume of Water Held by a Histogram

Problem: Pour water on a histogram, calculate the water volume the histogram can hold.

Solution: This is a relatively simple DP problem. Here we only give the main idea.
  • For a particular bar bi, if we know the highest bar on its left Li and highest bar on its right Ri.  If the height of bi is smaller than both Li and Ri, the water volume can be held on this bar is min(Li, Ri) - hi; otherwise, it can't hold water.
  • To calculate Li and Ri, we just need to record the maximum height we had observed so far from the left (and from the right). Therefore, a O(n) algorithm is straightforward here.

4 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. I should say your algorithm is not clear. :)

    ReplyDelete
  3. How do you keep track of largest number on both left and right side?

    ReplyDelete
  4. This algorithm requires O(n) space, but there is an algorithm that requires only O(1) space

    ReplyDelete