# Novel and easy to understand O(n) solution with full explanation in C++

``````class Solution {
public:
int trap(int A[], int n) {
int i, j, volume;
int sum = 0;

if (n <= 0) return 0;
// visited[i]: is equal sided container counted
bool visited[n] = {false};

// containers w/ left side strictly lower or equal to right side
i = 0;
while (i < n) {
// find right side, i.e., first higher point
for (j = i + 1, volume = 0; j < n && A[j] < A[i]; j++) {
volume += A[i] - A[j];
}
// found one container; this also holds when j = i + 1 since volume is 0
if (j < n) {
visited[i] = A[j] == A[i];
sum += volume;
}

i = j;
}

// containers w/ right side strictly lower
i = n - 1;
while (i >= 0) {
// find left side
for (j = i - 1, volume = 0; j >= 0 && A[j] < A[i]; j--) {
volume += A[i] - A[j];
}
// do not double count equal sided containers
if (j >= 0 && !visited[j])
sum += volume;

i = j;
}

return sum;
}
};
``````

• you can avoid using an extra bool vector by checking the if (a[j] >= a[i]) for left side and checking if (a[j] > a[i]) for right side. Otherwise, excellent solution!

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