# O(n) solution, O(1) space, simple c++ soln with comments.

• Basic idea is to keep a count of running water and everytime we encounter a closing wall, we store that water in a accumulated counter. If we never encounter a closing wall, that water is drained. For every value on the x-axis assume you store the current maximum of water, and then subtract the amount which was taken by the building.

``````class Solution {
public:
int trap(vector<int>& height) {
int total_blocks = height.size();

int accumulated = 0;
int current = 0;
int max = 0;

for (int i = 0; i < total_blocks; i++) {
if (height[i] > max) {
// Found a closing wall, accumulate
// the current water pool.
max = height[i];
accumulated += current;
current = 0;
} else {

current += max;

// Subtrack building
current -= min(max, height[i]);
}
}

// Last block is not the highest, so need to overflow whatever is left in current.
if (current && max != height[total_blocks - 1]) {
int i = total_blocks - 1;
int min = height[i];
while (height[i] != max) {
if (height[i] > min)
min = height[i];
// Drain the excess water
current -= (max - min);
i--;
}
}

accumulated += current;

return accumulated;
}
};
``````

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