5. Trapping Rain Water

Description

Remove Duplicates from Sorted Array
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.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Approach

• maintain max for both side and think this whatever is the highest if we minus the current then that much water can be there for that graph
• Time: O(n) Space: O(1)

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int res = 0, lm = height[l], rm = height[r];
        while (l < r) {
            if (lm < rm) {
                l++;
                lm = Math.max(lm,height[l]);
                res += lm - height[l];
            } else {
                r--;
                rm = Math.max(rm,height[r]);
                res += rm - height[r];
            }
        }
        return res;
    }
}

The key insight for 42. Trapping Rain Water is understanding how water is trapped at any single index $i$:

$\text{Water at }i=\min (\text{tallest bar to left},\text{tallest bar to right})-\text{height}[i]$

---

Brute Force Solution

Intuition

For every single bar, look left to find the max height so far, and look right to find the max height so far. Take the smaller of the two heights and subtract the current bar’s height.

class Solution {
    public int trap(int[] height) {
        int totalWater = 0;
        int n = height.length;
 
        for (int i = 0; i < n; i++) {
            int maxLeft = 0;
            for (int j = 0; j <= i; j++) {
                maxLeft = Math.max(maxLeft, height[j]);
            }
 
            int maxRight = 0;
            for (int j = i; j < n; j++) {
                maxRight = Math.max(maxRight, height[j]);
            }
 
            totalWater += Math.min(maxLeft, maxRight) - height[i];
        }
 
        return totalWater;
    }
}
 

Complexity

• Time Complexity: $O(N^2)$ — For each bar, we scan the entire array to the left and right.
• Space Complexity: $O(1)$ — No extra space used.

---

Most Optimized Solution (Two Pointers)

Intuition & Mental Model

Place two pointers at the outer boundaries (left = 0 and right = n - 1) and track the maximum heights seen from both sides (leftMax and rightMax).

• Always process the pointer with the smaller maximum height (leftMax < rightMax), because the shorter boundary acts as the bottleneck for water height.
• Move that pointer inward, update its running maximum height, and add leftMax - height[left] directly to the result. When a new peak is reached, leftMax - height[left] evaluates to 0, cleanly updating maximums without extra nested conditionals.

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int totalWater = 0;
        int leftMax = height[left], rightMax = height[right];
 
        while (left < right) {
            if (leftMax < rightMax) {
                left++;
                leftMax = Math.max(leftMax, height[left]);
                totalWater += leftMax - height[left];
            } else {
                right--;
                rightMax = Math.max(rightMax, height[right]);
                totalWater += rightMax - height[right];
            }
        }
 
        return totalWater;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single pass through the array with two pointers.
• Space Complexity: $O(1)$ — Constant extra space.