# Simple Java Solution O(n)

• public static int trap(int[] A) {
if(A==null || A.length<=1) return 0;
int lb[] = new int[A.length]; int rb[] = new int[A.length];
int maxFromLeft = 0; int maxFromRight = 0; int trappedWater = 0;
for(int i=0;i<A.length;i++) {
if(A[i]>maxFromLeft) maxFromLeft = A[i];
if(A[A.length-1-i]>maxFromRight) maxFromRight = A[A.length-1-i];
lb[i] = maxFromLeft; rb[A.length-1-i] = maxFromRight;
}
for(int i=1;i<A.length-1;i++) {
trappedWater = (Math.min(lb[i], rb[i])-A[i]>0)?trappedWater+Math.min(lb[i], rb[i])-A[i]:trappedWater;
}
return trappedWater;
}

1. The element lb[i] will store the left bound for the trapped water at position A[i]
2. The element rb[i] will store the right bound for the trapped water at position A[i]
3. The trapped water at position A[i] is given by the difference between the smaller bound for position A[i] (Math.min(lb[i], rb[i])), and the height at position A[i] (0 if this difference is negative).

• You can in fact improve this version further by reducing the memory needed for the one of the arrays and store the maximum in variable instead.

public class Solution {
public int trap(int[] A) {
if (A == null || A.length == 0) {
return 0;
}

final int N = A.length;
int left = A[0];

final int[] rigth = new int[N];
rigth[N - 1] = A[N - 1];
for (int ind = A.length - 2; ind >= 0; ind--) {
rigth[ind] = Math.max(A[ind], rigth[ind + 1]);
}

int trap = 0;
for (int ind = 0; ind < A.length; ind++) {
left = Math.max(left, A[ind]);
trap += Math.max(0, Math.min(left, rigth[ind]) - A[ind]);
}
return trap;
}

}

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