Course4all
Join us on telegram
Home/dsa/Two Pointers/Trapping Rain Water

Trapping Rain Water

Master this topic with zero to advance depth.

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Visual Representation

Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Bars: # # ## # # ## # ###### 010210132121 Water trapped (W): # # WW # #W##W###### Total Trapped: 6 units
Hard

Examples

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units of rain water.

Approach 1

Level I: Brute Force (Iterate per Unit of Water)

Intuition

For each element, the amount of water it can trap is determined by the maximum height to its left and its right. Water level = min(maxLeft, maxRight) - currentHeight.

⏱ O(N^2)💾 O(1)

Detailed Dry Run

Input: [0, 1, 0, 2] Index 2 (height 0): maxL=1, maxR=2. min(1, 2) - 0 = 1. Total = 1.

java
public int trap(int[] height) {
    int res = 0;
    for (int i = 0; i < height.length; i++) {
        int maxL = 0, maxR = 0;
        for (int j = 0; j <= i; j++) maxL = Math.max(maxL, height[j]);
        for (int j = i; j < height.length; j++) maxR = Math.max(maxR, height[j]);
        res += Math.min(maxL, maxR) - height[i];
    }
    return res;
}

⚠️ Common Pitfalls & Tips

O(N^2) is very slow for large inputs (N=10^5).

Approach 2

Level II: Precomputing Max Left/Right

Intuition

Instead of re-calculating maxLeft and maxRight for every index, we can precompute them using two arrays in O(N).

Create leftMax array where leftMax[i] stores max height from index 0 to i. Create rightMax array similarly for index i to n-1.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: [0, 1, 0, 2] leftMax: [0, 1, 1, 2] rightMax: [2, 2, 2, 2] Water at index 2: min(1, 2) - 0 = 1.

java
public int trap(int[] height) {
    int n = height.length;
    int[] lM = new int[n], rM = new int[n];
    lM[0] = height[0]; rM[n-1] = height[n-1];
    for (int i = 1; i < n; i++) lM[i] = Math.max(lM[i-1], height[i]);
    for (int i = n-2; i >= 0; i--) rM[i] = Math.max(rM[i+1], height[i]);
    int res = 0;
    for (int i = 0; i < n; i++) res += Math.min(lM[i], rM[i]) - height[i];
    return res;
}

⚠️ Common Pitfalls & Tips

O(N) space is used for the auxiliary arrays.

Approach 3

Level III: Optimal (Two Pointers)

Intuition

At any index i, the water trapped is min(maxLeft, maxRight) - height[i]. Instead of precalculating max arrays, we can use two pointers from ends. The pointer with the smaller max determines the water level for that side.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [4, 2, 0, 3, 2, 5]

  1. l=0, r=5. LMax=4, RMax=5. 4 < 5, move l to 1.
  2. l=1: height=2. Water += 4-2=2. l=2.
  3. l=2: height=0. Water += 4-0=4. l=3.
  4. l=3: height=3. Water += 4-3=1. l=4.
  5. l=4: height=2. Water += 4-2=2. l=5. Total water: 2+4+1+2 = 9.
java
public class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, water = 0;
        int leftMax = 0, rightMax = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= leftMax) leftMax = height[l];
                else water += leftMax - height[l];
                l++;
            } else {
                if (height[r] >= rightMax) rightMax = height[r];
                else water += rightMax - height[r];
                r--;
            }
        }
        return water;
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the update condition: only add water if the current height is less than the current side's max height.

← Previous QuestionFind the Duplicate Number
Next Question →Median of Two Sorted Arrays