Haskell solution to http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/

rain_ordo_n.hs

rainSolver = solve 0 . zipWithRightMax

zipWithRightMax xs = zip xs maxVals
  where
    rev = reverse xs
    (maxVals, _) = foldl maxFold ([], head rev) rev
    maxFold (acc, maxVal) x = (maxVal:acc,maxFromHere)
      where
        maxFromHere = max maxVal x

solve acc [] = acc
solve acc (x:xs)
  | xs' == [] = solve acc xs -- no right border -> this x cannot be left border
  | otherwise = solve (acc+area) xs'
  where
    (val, rightMax) = x
    height = min val rightMax
    (elems',xs') = span ((<height).fst) xs
    elems = fst $ unzip elems'
    area = (length elems * height) - (sum elems)

rainhaskell.hs

rainSolver = solve 0

solve acc [] = acc
solve acc (x:xs)
  | xs' == [] = solve acc xs -- no right border -> this x cannot be left border
  | otherwise = solve (acc+area) xs'
  where
    height      = minimum [x, maximum xs]
    (elems,xs') = span (<height) xs
    area        = (length elems * height) - (sum elems)

Man, I need to learn Haskell :)

This is O(n^2) without precomputing max of all the suffixes, isn't it

EDIT: Actually, more complicated than that. The span is also linear time =/

@Bontrey: Yes, it is.

@Bontrey: The span doesn't make it O(n^2).
Consider these extremes:
Take one elements n times.
Take all elements 1 time.

Oh yeah. Good point. Each element is only segmented out once