> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/42.-trapping-rain-water.md).

# 42. Trapping Rain Water

{% hint style="info" %}

```java
        // let w(i) represent the amount of water trapped at position i
        // h(left) represent the highest height on left of i, 
        // h(right) represent the highest height on the right of i,
        // w(i) = min(h(left), h(right)) - h(i);
```

{% endhint %}

### DP:

```java
class Solution {
    public int trap(int[] height) {
        int[] l = new int[height.length];
        int[] r = new int[height.length];
        int leftMax = 0;
        for(int i = 0; i<height.length; i++){
            leftMax = i == 0 ?  height[i] : Math.max(l[i-1], height[i]);
            l[i] = leftMax;
        }
        
        int rightMax = 0;
        for (int j= height.length-1; j>=0; j--){
            rightMax = j == height.length-1 ? height[j] : Math.max(height[j], r[j+1]);
            r[j] = rightMax;
        }
        
        int sum = 0;
        for (int k = 0; k<height.length; k++){
            sum += Math.min(l[k], r[k])-height[k];
        }
        return sum;
    }
}
```

### Two pointers:

```java
class Solution {
    public int trap(int[] height) {
        int l = 0;
        int r = height.length-1;
        
        //represent the maxium height in the range [0, l];
        int maxL = 0;
        //represent the maxium height in the range [r, height.length-1];
        int maxR = 0;
        int sum = 0;
        while(l<r){
            maxL = Math.max(maxL, height[l]);
            maxR = Math.max(maxR, height[r]);
            if (maxL<=maxR){
                sum+=maxL-height[l];
                l++;
            }else{
                sum += maxR-height[r];
                r--;
            }
        }
        return sum;
    }
}
```