# This is why I *LOVE* C++11! (O(n) solution with heavy use of STL and no loops)

• ``````//Divide the input into two sections of (kinda) monotonically increasing sequences
//then do a left fold from the lhs->max and a right fold from max<-rhs
class Solution {
typedef pair<int, int> t_ACCNMAX; //(sum so far, maximum-height-so-far)
public:
int trap(vector<int>& height) {
if (height.size() == 0 || height.size() == 1) return 0;

int max = std::accumulate(height.begin(), height.end(), std::numeric_limits<int>::min(),
[] (const int& acc, const int& val) -> int {
return (acc > val ? acc : val);
});
auto maxrit = std::find(height.rbegin(), height.rend(), max);
auto maxfit = (maxrit + 1).base();

std::function<t_ACCNMAX (t_ACCNMAX, int)> foldFunc = [] (t_ACCNMAX summaxht, int ht) -> t_ACCNMAX {
int maxht   = summaxht.second;
int sumsofar= summaxht.first;
int newsum = maxht > ht ? (maxht - ht) : 0;
return std::make_pair(sumsofar + newsum, ht > maxht ? ht : maxht);
};

t_ACCNMAX accumulator = std::make_pair(0, 0);
t_ACCNMAX lhsMono = std::accumulate(height.begin(),  maxfit, accumulator, foldFunc);
t_ACCNMAX rhsMono = std::accumulate(height.rbegin(), maxrit, accumulator, foldFunc);

return (lhsMono.first + rhsMono.first);
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.