# Simple Java O(n) time O(n) space solution

• public class Solution {
// [0,1,0,2,1,0,1,3,2,1,2,1]
// lmax (left -> right) [0,1,1,2,2,2,2,3,3,3,3,3]
// rmax (right -> left) [3,3,3,3,3,3,3,3,2,2,2,1]

``````// left -> right
// sum1: (sum(lmax - height))   0+1+1+0+1+2+1+0+1+2+1+2 = 11

// right -> left
// sum2:   for lmax > rmax
//         (sum(lmax - rmax))   2+1+1+1+stop = 5

// vol = sum1 - sum2

public int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int len = height.length;
int vol = 0;

int[] lmax = new int[len];
lmax[0] = height[0];

for (int i = 1; i < len; i++) {
lmax[i] = Math.max(lmax[i - 1], height[i]);
vol += lmax[i] - height[i];
}

int[] rmax = new int[len];
rmax[len - 1] = height[len - 1];

for (int i = len - 1; i > 0; i--) {
if (rmax[i] < lmax[i]) {
vol -= lmax[i] - rmax[i];
} else {
return vol;
}
rmax[i - 1] = Math.max(rmax[i], height[i - 1]);
}

return vol;
}
``````

}

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