Easy to read Java solutions O(n) time and O(1) space

• Pseudocode

``````/*
start at ends
keep lMax, rMax
while lo < hi
lMax = max(lMax, height[lo])
rMax = max(rMax, height[hi])
water @ lo = max(min(lMax, rMax) - height[lo], 0)
water @ hi = max(min(lMax, rMax) - height[hi], 0)
if lMax == rMax
lo++ hi--
else if lMax < rMax
lo++
else
hi++
*/
``````

O(n) space initial solution

``````public int trap(int[] height) {
int[] water = new int[height.length];
int lMax = 0;
int rMax = 0;
int lo = 0;
int hi = height.length - 1;

while (lo <= hi) {
lMax = Math.max(lMax, height[lo]);
rMax = Math.max(rMax, height[hi]);
int lrMin = Math.min(lMax, rMax);
water[lo] = Math.max(lrMin - height[lo], 0);
water[hi] = Math.max(lrMin - height[hi], 0);

if (lMax == rMax) {
lo++; hi--;
} else if (lMax < rMax) {
lo++;
} else {
hi--;
}
}

// sum over water
int sum = 0;
for (int n : water) {
sum += n;
}
return sum;
``````

O(1) space optimized solution

``````public int trap(int[] height) {
int sum = 0;
int lMax = 0;
int rMax = 0;
int lo = 0;
int hi = height.length - 1;

while (lo < hi) {
lMax = Math.max(lMax, height[lo]);
rMax = Math.max(rMax, height[hi]);
int lrMin = Math.min(lMax, rMax);

if (lMax < rMax) {
sum += Math.max(lrMin - height[lo], 0);
lo++;
} else {
sum += Math.max(lrMin - height[hi], 0);
hi--;
}
}

return sum;
}
``````

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