The Watermark Problem
You are given a bar graph as a list of integers. Write a function that returns the amount of water the bar graph would hold if you poured water over the top.
Consider the following bar graph
_ . . . _
_ .  _  
_ .   _ _ 
_ _ _ 
0 1 0 2 0 3 1 2 1 3
This graph can hold 8 units of water. The dots in the graph mark the level of water for a given column.
Input.
The input consists of one or more bar graphs. Each bar graph is given
on a separate line as a list of space separated integers. Each line
is terminated by a newline character (\n
) and the input is
terminated by EOF.
0 1 0 2 0 3 1 2 1 3
0 1 0 1 0
Output.
The output consists of the amount of units of water that each bar
graph can hold. Each amount appears in the line that corresponds to
its graph. Each line is terminated by a newline character (\n
) and
the output is terminated by EOF.
8
1
Check your solution online
Before you read our solution, try to solve the problem on your own. Remember that practice makes perfect.
Click here to check your solution online at The Book of Problems.
20180709 The Book of Problems currently supports Ruby, Python, Elixir, Java, C, OCaml, and now C++!
Problem Structure
Given a histogram, the structure of the histogram consists of a sequence of valleys and peaks that begins with an edge and ends with another. Consider the following example histogram.
peaks


    
  v  
 v _ v v
v _ . . _ . . _
_ .   _  _ 
_ _ _ _ 
0 1 0 2 0 3 1 2 0 1 2 < value
0 1 2 3 4 5 6 7 8 9 10 < index
^ ^ ^ ^ ^^^ ^
     
  
  
 valleys 
 


edges
When we pour water over the histogram, a unit of water either remains trapped or escapes the histogram. A unit of water remains in the histogram when it is trapped in a valley. In the example, every space below the dots contains water. A unit of water escapes the histogram by overflowing the left or the right edge. In the example, water above the dots or the peaks overflows.
The direction of overflow is determined by the highest peak. In the example, the highest peak is at index 5. Water poured to the left of the highest peak that overflows does so by the left edge. For water poured to the right, water overflows to the right.
Approach
We approach the problem by splitting the histogram by the first highest peak and solving each part.
To illustrate the approach, consider the highest peak in the example histogram.
highest peak

v
_
_   _ _
_    _  _ 
_ _ _ _ 
0 1 0 2 0 3 1 2 0 1 2 < value
0 1 2 3 4 5 6 7 8 9 10 < index
The splitting of the histogram gives the following lefthand side.
_
_  
_    
_ _ _ 
0 1 0 2 0 3 < value
0 1 2 3 4 5 < index
^

left edge of the histogram
We solve the lefthand side by detecting each valley and computing its corresponding amount of water.
We detect valleys in the following way. We move from left to right. We record the position of the left edge of the histogram (index 0 in the example) and find the first value that is higher or equal (index 1 in the example). Those positions are the left and right edges of a valley.
_
_  
_    
_ _ _ 
0 1 0 2 0 3 < value
0 1 2 3 4 5 < index
^ ^
 
 right edge of a valley
left edge of a valley
We accumulate the amount of water that the valley holds. In our example the length of the valley is 0 and thus the amount of water is 0. Next, we record the position of the right edge (index 1) and look for a value that is higher or equal (index 3).
_
_  
_    
_ _ _ 
0 1 0 2 0 3 < value
0 1 2 3 4 5 < index
^ ^
 
 right edge of a valley
left edge of a valley
We accumulate the corresponding amount of water (1 unit of water). We repeat the process until we get to the end.
Detecting valleys by finding the first value higher or equal to the current left edge works because water can only overflow to the left.
We solve the righthand side of the histogram by reversing it and applying the same procedure. Consider the reverse of the righthand side of the example.
highest peak

v
_
_ _  
 _  _ 
 _ 
2 1 0 2 1 3 < value
0 1 2 3 4 5 < index
Implementation
The following is our Ruby implementation of the approach.
The runtime of our implementation if $@O(n)@$ where $@n@$ is the length of the histogram.
Want to read more?
I love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?
If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.