# A two-pass O(n) solution inspired by one solution of [Candy]

• You'd better solve the Candy puzzle first.

``````class Solution {
public:
int trap(int A[], int n) {
vector<int> v(n);
for (int i = 0; i < n; i++) v[i] = A[i];
int result = 0;
for (int l = 0, r = 1; r < n; r++) {
if (v[l] < 0) {
l++;
continue;
}
if (v[l] <= v[r]) {
for (int i = l + 1; i < r; i++) {
result += v[l] - v[i];
v[i] = v[l];
}
l = r;
}
}
for (int l = n - 2, r = n - 1; l >= 0; l--) {
if (v[r] < 0) {
r--;
continue;
}
if (v[l] >= v[r]) {
for (int i = r - 1; i > l; i--) {
result += v[r] - v[i];
v[i] = v[r];
}
r = l;
}
}
return result;
}
};
``````
1. Loop from left to right, if `A[left] > 0` and `A[right] >= A[left]`, add water to the container until `A[i] == A[left]`, then find the next container starting after `A[right]`.
2. Loop from right to left, if `A[right] > 0` and `A[left] >= A[right]`, add water to the container until `A[i] == A[right]`, then find the next container starting before `A[left]`.
3. Return the volume of the total water.

Demo:

``````|      #           |      #           |      #           |      #           |
|#    ##      #    |#~~~~##      #    |#~~~~##      #    |#~~~~##~~~~~~#    |
|#   ### #    #    |#~~~### #    #    |#~~~### #    #    |#~~~###~#~~~~#    |
|#  #### # #  # #  |#~~#### # #  # #  |#~~#### # #  #~#  |#~~####~#~#~~#~#  |
|# ##### # #### ###|#~##### # #### ###|#~##### # ####~###|#~#####~#~####~###|
|401234503021140211|401234503021140211|401234503021140211|401234503021140211|``````

• Helps a lot, thanks!

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