Trapping Rain Water

Hard

Python

def trap(height):
    l,r=0,len(height)-1
    lmax=rmax=water=0
    while l<r:
        if height[l]<=height[r]:
            if height[l]>=lmax: lmax=height[l]
            else: water+=lmax-height[l]
            l+=1
        else:
            if height[r]>=rmax: rmax=height[r]
            else: water+=rmax-height[r]
            r-=1
    return water

Java

public int trap(int[] height){
    int l=0,r=height.length-1,lmax=0,rmax=0,water=0;
    while(l<r){
        if(height[l]<=height[r]){
            if(height[l]>=lmax) lmax=height[l];
            else water+=lmax-height[l];
            l++;
        } else {
            if(height[r]>=rmax) rmax=height[r];
            else water+=rmax-height[r];
            r--;
        }
    } return water;
}

Key Insight

O(1) space. Python chain assign. Algorithm identical.

Python → Java Differences

lmax=rmax=water=0 chain assign
Two-pointer O(1) space identical
Separate Java declarations

Python

def trap(height):
    l,r=0,len(height)-1
    lmax=rmax=water=0
    while l<r:
        if height[l]<=height[r]:
            if height[l]>=lmax: lmax=height[l]
            else: water+=lmax-height[l]
            l+=1
        else:
            if height[r]>=rmax: rmax=height[r]
            else: water+=rmax-height[r]
            r-=1
    return water

Java

public int trap(int[] height){
    int l=0,r=height.length-1,lmax=0,rmax=0,water=0;
    while(l<r){
        if(height[l]<=height[r]){
            if(height[l]>=lmax) lmax=height[l];
            else water+=lmax-height[l];
            l++;
        } else {
            if(height[r]>=rmax) rmax=height[r];
            else water+=rmax-height[r];
            r--;
        }
    } return water;
}

Algorithm Steps

1. Process shorter side
2. Accumulate water
3. Move inward

← Previous All Two Pointers Next →