Instantly share code, notes, and snippets.

# olajep/rain_ordo_n.hs Last active Aug 23, 2019

 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 ((
 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 (

### qazwsxpawel commented Oct 30, 2013

 Man, I need to learn Haskell :)

### Bontrey commented Oct 30, 2013

 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 =/
Owner Author

### olajep commented Oct 30, 2013

 @Bontrey: Yes, it is.
Owner Author

### olajep commented Oct 30, 2013

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

### Bontrey commented Oct 30, 2013

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