# A different O(n) approach - easy to understand and simple code

• ``````class Solution {
public:
int trap(int a[], int n) {
int i, res = 0;
if(!n) return res;
vector<int> ltr(n, 0), rtl(n, 0);
for(i = 1, ltr[0] = a[0]; i < n; i++)
ltr[i] = max(ltr[i-1], a[i]);
for(i = n - 2, rtl[n-1] = a[n-1]; i >= 0; i--)
rtl[i] = max(rtl[i+1], a[i]);
for(i = 0; i < n; i++)
res += min(ltr[i], rtl[i]) - a[i];
return res;
}
};
``````

observation:

scan A both from left to right and right to left, record the largest seen during the scan; then for each position the water level should be the min of the 2 large value.

• res += min(ltr[i] - a[I], rtl[i]) - a[i];

• the same principle with Java.

``````    if(A.length==0) return 0;

int[] A1=new int[A.length];
int[] A2=new int[A.length];
int max=A[0];
for(int i =0;i<A.length;i++) {
if(A[i]>max) max=A[i];
A1[i]=max;
}
max=A[A.length-1];
for(int i=A.length-1;i>=0;i--){
if(A[i]>max) max=A[i];
A2[i]=max;
}
int sum=0;
for(int i=0;i<A.length;i++){
sum=sum+Math.min(A1[i],A2[i])-A[i];
}
return sum;
}
``````

• truly easy to understand

• @qddpx Amazing solution, you just made my day with this solution. Thank you :)

• This post is deleted!

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