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)

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