Java Solution with O(n) time and O(1) space


  • 3

    Very classic Two Pointer question.
    If we want to trap water for one point i, we need to satisfy two conditions:

    • 1 leftBar > height[i]

    • 2 rightBar > height[i]

    The water trapped = Min(leftBar, rightBar) - height[i]
    So the key is always trap water from the side of lower bar.

    public class Solution {
        public int trap(int[] height) {
            int sum=0;
            int n=height.length;
            if(n<3) return 0;
            
            int left=0, right=n-1;
            int leftBar = height[left++];
            int rightBar = height[right--];
            
            while(left<=right){
                if(leftBar>rightBar){
                    if(height[right]<rightBar) 
                        sum+=rightBar - height[right];
                    else
                        rightBar=height[right];
                    right--;
                }else{
                    if(height[left]<leftBar)
                        sum+=leftBar - height[left];
                    else
                        leftBar=height[left];
                    left++;
                }
            }
            return sum;
        }
    }
    
    

  • 0

    Straightforward! Easy to understand!


Log in to reply
 

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