Water collected between towers

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

Solution 2:

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.