Java Simplest Code + Drawing - O(n) time, O(1) space


  • 0
    M
     public int trap(int[] height) {
            
            // smaller or equal
            //       __   
            // __   |  |
            //|  |~~|  |
            int optional = 0, max=0, res = 0;
            for (int h : height ){
                if (h >= max){
                    res += optional;
                    optional = 0;
                    max = h;
               }else
                    optional += (max-h);
            }
            
            // bigger
            // __
            //|  |   __
            //|  |~~|  | 
            max = optional = 0;
            for (int i = height.length-1; i>=0; i-- ){
                int h = height[i];
                if (h > max){
                    res += optional;
                    optional = 0;
                    max = h;
                }else
                    optional += (max-h);
            }
            return res;
            
        }
    

Log in to reply
 

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