Easy to read Java solutions O(n) time and O(1) space


  • 0
    H

    Pseudocode

    /*
        start at ends
        keep lMax, rMax
        while lo < hi
            lMax = max(lMax, height[lo])
            rMax = max(rMax, height[hi])
            water @ lo = max(min(lMax, rMax) - height[lo], 0)
            water @ hi = max(min(lMax, rMax) - height[hi], 0)
            if lMax == rMax
                lo++ hi--
            else if lMax < rMax
                lo++
            else 
                hi++
        */
    

    O(n) space initial solution

    public int trap(int[] height) {
            int[] water = new int[height.length];
            int lMax = 0;
            int rMax = 0;
            int lo = 0;
            int hi = height.length - 1;
            
            while (lo <= hi) {
                lMax = Math.max(lMax, height[lo]);
                rMax = Math.max(rMax, height[hi]);
                int lrMin = Math.min(lMax, rMax);
                water[lo] = Math.max(lrMin - height[lo], 0);
                water[hi] = Math.max(lrMin - height[hi], 0);
                
                if (lMax == rMax) {
                    lo++; hi--;
                } else if (lMax < rMax) {
                    lo++;
                } else {
                    hi--;
                }
            }
            
            // sum over water
            int sum = 0;
            for (int n : water) {
                sum += n;
            }
            return sum;
    

    O(1) space optimized solution

    public int trap(int[] height) {
            int sum = 0;
            int lMax = 0;
            int rMax = 0;
            int lo = 0;
            int hi = height.length - 1;
            
            while (lo < hi) {
                lMax = Math.max(lMax, height[lo]);
                rMax = Math.max(rMax, height[hi]);
                int lrMin = Math.min(lMax, rMax);
                
                if (lMax < rMax) {
                    sum += Math.max(lrMin - height[lo], 0);
                    lo++;
                } else {
                    sum += Math.max(lrMin - height[hi], 0);
                    hi--;
                }
            }
            
            return sum;
        }
    

Log in to reply
 

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