# O(n) time O(n) space DP Java Solution, and O(n) time O(1) space Java Solution

• ``````public int trap(int[] height) {
int result = 0;
int[] left = new int[height.length];
int[] right = new int[height.length];
for (int i = 0; i < height.length; i++) {
left[i] = (i == 0 || height[i] > left[i - 1]) ? height[i] : left[i - 1];
}
for (int i = height.length - 1; i >= 0; i--) {
right[i] = (i == height.length - 1 || height[i] > right[i + 1]) ? height[i] : right[i + 1];
}
for (int i = 0; i < height.length; i++) {
result += Math.max(0, Math.min(left[i], right[i]) - height[i]);
}
return result;
}

public int trap(int[] height) {
if (height.length == 0) {
return 0;
}
int left = 0;
int right = height.length - 1;
int result = 0;
int leftMax = height[left];
int rightMax = height[right];
while (left < right) {
if (height[left] < height[right]) {
result += Math.max(0, leftMax - height[left]);
leftMax = Math.max(leftMax, height[left]);
left++;
} else {
result += Math.max(0, rightMax - height[right]);
rightMax = Math.max(rightMax, height[right]);
right--;
}
}
return result;
}``````

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