Water collected between towers

Here's an efficient solution in Haskell

rainfall :: [Int] -> Int
rainfall xs = sum (zipWith (-) mins xs)
    where mins = zipWith min maxl maxr
          maxl = scanl1 max xs
          maxr = scanr1 max xs

it uses the same two-pass scan algorithm mentioned in the other answers.

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];

Refer this website for code, its really plain and simple http://learningarsenal.info/index.php/2015/08/21/amount-of-rain-water-collected-between-towers/

Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units

Explanation

Each tower can hold water upto a level of smallest height between heighest tower to left, and highest tower to the right.

Thus we need to calculate highest tower to left on each and every tower, and likewise for the right side.

Here we will be needing two extra arrays for holding height of highest tower to left on any tower say, int leftMax[] and likewise for right side say int rightMax[].

STEP-1

We make a left pass of the given array(i.e int tower[]),and will be maintaining a temporary maximum(say int tempMax) such that on each iteration height of each tower will be compared to tempMax, and if height of current tower is less than tempMax then tempMax will be set as highest tower to left of it, otherwise height of current tower will be assigned as the heighest tower to left and tempMax will be updated with current tower height,

STEP-2

We will be following above procedure only as discussed in STEP-1 to calculate highest tower to right BUT this times making a pass through array from right side.

STEP-3

The amount of water which each tower can hold is-

(minimum height between highest right tower and highest left tower) – (height of tower)