title: Water collected between towers
body: <p>I recently came across an interview question asked by Amazon and I am not able to find an optimized algorithm to solve this question:</p>
  
  <p>You are given an input array whose each element represents the height of a line towers. The width of every tower is 1. It starts raining. How much water is collected between the towers?</p>
  
  <p>Example</p>
  
  <pre><code>Input: [1,5,3,7,2] , Output: 2 units
  Explanation: 2 units of water collected between towers of height 5 and 7
  
     *
     *
   *w*
   *w*
   ***
   ****
  *****
  </code></pre>
  
  <p>Another Example</p>
  
  <pre><code>Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units 
  Explanation= 2 units of water collected between towers of height 5 and 7 +
               4 units of water collected between towers of height 7 and 6 + 
               1 units of water collected between towers of height 6 and 5 +
               2 units of water collected between towers of height 6 and 9 +
               4 units of water collected between towers of height 7 and 9 +
               1 units of water collected between towers of height 9 and 2.
  </code></pre>
  
  <p>At first I thought this could be solved by Stock-Span Problem (<a href="http://www.geeksforgeeks.org/the-stock-span-problem/" rel="noreferrer">http://www.geeksforgeeks.org/the-stock-span-problem/</a>) but I was wrong so it would be great if anyone can think of a time-optimized algorithm for this question.</p>