Java 10 line O(n) time O(1) space, beat 90%


  • 0
    A
    public int trap(int[] height) {
        int res = 0;
        if(height==null || height.length<=2) return res;
        int lftMax = height[0], rgtMax = height[height.length-1], left = 0, right = height.length-1;
        while(left<right){
            if(height[left]>=lftMax) lftMax = height[left];
            else res += lftMax - height[left];
            if(height[right]>=rgtMax) rgtMax = height[right];
            else res += rgtMax - height[right];
            if(lftMax<rgtMax) 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.