Water collected between towers

Question

I recently came across an interview question asked by Amazon and I am not able to find an optimized algorithm to solve this question:

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?

Example

Input: [1,5,3,7,2] , Output: 2 units Explanation: 2 units of water collected between towers of height 5 and 7     *    *  *w*  *w*  ***  **** ***** 

Another Example

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. 

At first I thought this could be solved by Stock-Span Problem (http://www.geeksforgeeks.org/the-stock-span-problem/) but I was wrong so it would be great if anyone can think of a time-optimized algorithm for this question.

Answer 1

Once the water's done falling, each position will fill to a level equal to the smaller of the highest tower to the left and the highest tower to the right.

Find, by a rightward scan, the highest tower to the left of each position. Then find, by a leftward scan, the highest tower to the right of each position. Then take the minimum at each position and add them all up.

Something like this ought to work:

int tow[N]; // nonnegative tower heights int hl[N] = {0}, hr[N] = {0}; // highest-left and highest-right for (int i = 0; i < n; i++) hl[i] = max(tow[i], (i!=0)?hl[i-1]:0); for (int i = n-1; i >= 0; i--) hr[i] = max(tow[i],i<(n-1) ? hr[i+1]:0); int ans = 0; for (int i = 0; i < n; i++) ans += min(hl[i], hr[i]) - tow[i];