# Concise O(1) space Java Solution

• Idea: The water being trapped is determined by

Min(left boundary, right boundary) * length - any smaller bar in between

Thus, keep two pointers representing left boundary and right boundary, add the rectangle area first, deleting any smaller bar in between. Each time a larger bar is met, update boundary accordingly.

The variable pre is to record the height of previous boundary.

``````public class Solution {
public int trap(int[] A) {
int left = 0 , right = A.length-1;
int sum = 0;
int pre = 0;
while(left < right){
sum += (Math.min(A[left], A[right])-pre) * (right-left-1);
pre = Math.min(A[left],A[right]);
if(A[left] > A[right]){
int temp = right-1;
while(left < temp && A[temp] <= pre){sum-=A[temp];temp--;}
if(left < temp) sum -= pre;
right = temp;
}else{
int temp = left+1;
while(temp < right && A[temp] <= pre){sum-=A[temp];temp++;}
if(temp < right) sum -= pre;
left = temp;
}
}
return sum;
}
}``````

• Very smart idea! Thanks for your sharing!

• Hi,
Brilliant!
I wrote a version based on your idea without the inner loops (because it's easier for me to understand it this way):

``````int trap(int A[], int n) {
int res = 0, left = 0, right = n-1, prevHeight = 0;

while(left < right) {
int height = (A[left] < A[right] ? A[left] : A[right]);
if(height > prevHeight) {
res -= prevHeight;
res += (right - left -1) * (height - prevHeight);
prevHeight = height;
} else {
res -= height;
}
if(A[left] <= A[right]) {
left++;
} else {
right--;
}
}
return res;
}
``````

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