Concise O(1) space Java Solution


  • 3
    S

    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;
        }
    }

  • 0
    H

    Very smart idea! Thanks for your sharing!


  • 7
    Y

    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;
    }
    

Log in to reply
 

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