Java 2 ms, one pass, one loop, two pointers


  • 1
    P

    Since the code for the left and right cases is identical except l/r ++/-- it most likely can be compacted.

    public int trap(int[] height) 
    {
        if(height.length == 0)
            return 0;
            
        int res = 0, l = 0, r = height.length - 1;
        int currentMinHeight = Math.min(height[l], height[r]);
        boolean fromLeft = currentMinHeight == height[l];
        while(l < r)
        {
            if(fromLeft)
            {
                if(height[l] > currentMinHeight)
                {
                    currentMinHeight = Math.min(height[l], height[r]);
                    fromLeft = (currentMinHeight == height[l]);
                    if(fromLeft)
                        ++l;
                }
                else
                {
                    res += currentMinHeight - height[l++];
                }
            }
            else // from right
            {
                if(height[r] > currentMinHeight)
                {
                    currentMinHeight = Math.min(height[l], height[r]);
                    fromLeft = (currentMinHeight == height[l]);
                    if(!fromLeft)
                        --r;
                }
                else
                {
                    res += currentMinHeight - height[r--];
                }
            }
        }
        
        return res;
    }

Log in to reply
 

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