Last active
August 23, 2019 11:37
-
-
Save olajep/7236551 to your computer and use it in GitHub Desktop.
Haskell solution to http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@Bontrey: The span doesn't make it O(n^2).
Consider these extremes:
Take one elements n times.
Take all elements 1 time.