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.

2018-07-09 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 left-hand side.

          _
      _  | |
  _  | | | |
_| |_| |_| |
0 1 0 2 0 3  <-- value
0 1 2 3 4 5  <-- index
^
|
left edge of the histogram

We solve the left-hand 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 right-hand side of the histogram by reversing it and applying the same procedure. Consider the reverse of the right-hand 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.

#!/usr/bin/env ruby

def volume_of_segment h, s, e
  watermark = [h[s], h[e]].min
  volume = 0
  h[(s+1)..(e-1)].each do |n|
    volume += watermark - n
  end
  return volume
end

def volume_increasing h
  return 0 if h.empty?
  volume = 0
  max = h[0]
  maxi = 0
  h[1..-1].each_with_index do |n, i|
    if n >= max
      volume += volume_of_segment h, maxi, (i + 1)
      max = n
      maxi = (i + 1)
    end
  end
  return volume
end

def volume h
  return 0 if h.empty?
  max = h.max
  maxi = h.find_index max
  first_half = h[0..maxi]
  second_half = h[maxi..-1].reverse
  vfh = volume_increasing(first_half)
  vsh = volume_increasing(second_half)
  return vfh + vsh
end

while true
  h = readline.strip.split(' ').map(&:to_i) rescue break
  puts volume h
end

The run-time 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, the kind you find in coding interviews. 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.

Comments