Share my short solution.


  • 199
    Y

    Keep track of the maximum height from both forward directions backward directions, call them leftmax and rightmax.


    public int trap(int[] A){
        int a=0;
        int b=A.length-1;
        int max=0;
        int leftmax=0;
        int rightmax=0;
        while(a<=b){
            leftmax=Math.max(leftmax,A[a]);
            rightmax=Math.max(rightmax,A[b]);
            if(leftmax<rightmax){
                max+=(leftmax-A[a]);       // leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored
                a++;
            }
            else{
                max+=(rightmax-A[b]);
                b--;
            }
        }
        return max;
    }

  • 2
    M

    It's a great answer, but can you give more detail about this method?


  • 38
    K

    The idea is: I calculated the stored water at each index a and b in my code. At the start of every loop, I update the current maximum height from left side (that is from A[0,1...a]) and the maximum height from right side(from A[b,b+1...n-1]). if(leftmax<rightmax) then, at least (leftmax-A[a]) water can definitely be stored no matter what happens between [a,b] since we know there is a barrier at the rightside(rightmax>leftmax). On the other side, we cannot store more water than (leftmax-A[a]) at index a since the barrier at left is of height leftmax. So, we know the water that can be stored at index a is exactly (leftmax-A[a]). The same logic applies to the case when (leftmax>rightmax). At each loop we can make a and b one step closer. Thus we can finish it in linear time.


  • 0
    W

    Great answer. But can you explain why always move the shorter bar to make a and b one step closer? Thank you very much!


  • 1
    W

    Never mind. I got it! Because the volume always depends on the shorter bar.


  • 0
    C

    Brilliant idea, kudos!


  • 0
    D

    My solution looks similar, the water trapped always decided by shorter bar

    Then use two pointer left and right to iterate all bars. And use two variable rightmax,leftmax to keep track of the largest length bar

    The core logic is:

    if(leftmax < rightmax) {
        max += leftmax -A[left];
        left++;
    }else {
        max += rightmax - A[right];
        right--;
    }
    
    
    // code starts here
    public int trap(int[] A) {
        if(A==null || A.length==0) return 0;
        int leftmax = 0;
        int rightmax = 0;
        int left = 0;
        int right = A.length-1;
        int max = 0;
        while(left<right) {
            leftmax = Math.max(leftmax, A[left]);
            rightmax = Math.max(rightmax, A[right]);
            if(leftmax < rightmax) {
                max += leftmax -A[left];
                left++;
            }else {
                max += rightmax - A[right];
                right--;
            }
        }
        return max;
    }

  • 0
    Z

    I wish every explanation on this website is as clear as this one. Great job!


  • 0
    L

    Thank you for this. Clean code and nice explanation !


  • 0
    O
    This post is deleted!

  • 0
    E

    @kyle.yu Easy to understand, thank you!


  • 0
    L

    I think the following organization could be easier for reasoning the algorithm idea. OP code updates the rmax/lmax before comparison/branching, this somehow changes the meaning of the two variables into something other than known maximums trapping the current pointers.

    public class Solution {
        public int trap(int[] arr) {
            int sum = 0;
            int lmax = 0;
            int rmax = 0;
            int i=0;
            int j = arr.length-1;
            while (i<=j) {
                if (lmax>=rmax) {
                    int delta = rmax - arr[j];
                    if (delta>0) {
                        sum += delta;
                    }
                    rmax = Math.max(rmax, arr[j]);
                    j--;
                } else {
                    int delta = lmax - arr[i];
                    if (delta>0)
                        sum+= delta;
                    lmax = Math.max(lmax, arr[i]);
                    i++;
                }
            }
            
            return sum;
        }
    }
    

  • 0
    I

    Great answer! But while(a<b) is enough, the situation a=b would never count anyway.


  • 7

    alt text


  • 0
    R

    Remarkable!!


  • 0
    F

    Excellent method! Thanks for explaining

    Translated to python

    class Solution(object):
        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            leftCursor, rightCursor = 0, len(height)-1
            leftMax, rightMax, storedWater = 0, 0, 0
            
            while (leftCursor <= rightCursor):
                leftMax = max(leftMax, height[leftCursor])
                rightMax = max(rightMax, height[rightCursor])
                if leftMax < rightMax:
                    storedWater += leftMax - height[leftCursor]
                    leftCursor += 1
                else:
                    storedWater += rightMax - height[rightCursor]
                    rightCursor -= 1
                    
            return storedWater
    

Log in to reply
 

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