Java Solution O(n) 20ms with explanation


  • 0
    M
    class Solution {
        public int trap(int[] height) {
            if (height.length == 0) {
                return 0;
            }
            
            int water = 0;
            int l = 0;
            int r = height.length-1;
            int maxL = height[l]; // max height observed starting from the left
            int maxR = height[r]; // max height observed starting from the right
            while (l <= r)
            {
                if (maxL < maxR) {
                    // In this case, the water height is at most maxL
                    if (maxL > height[l]) {
                        water += maxL - height[l];
                    } else {
                        maxL = height[l];
                    }
                    l++;
                } else {
                    // In this case, the water height is at most maxR
                    if (maxR > height[r]) {
                        water += maxR - height[r];
                    } else {
                        maxR = height[r];
                    }
                    r--;
                }
            }
            
            return water;
        }
    }
    

Log in to reply
 

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