Algorithm-Day07-Trapping-Rain-Water-lc-42

🧩 Problem Description

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:

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

---

💡 Brute Force (Too Slow)

For each index i, calculate:

• The max height to the left
• The max height to the right
• Water at i = min(leftMax, rightMax) - height[i]

But this takes O(n²) time.

---

💡 Optimized Approach 1: Precomputed Arrays (Prefix Max)

We use two arrays:

• leftMax[i]: max height to the left (including i)
• rightMax[i]: max height to the right (including i)

Then compute trapped water at each index.

🔢 Java Code (Prefix Max)

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return total;
    }
}

⏱ Complexity

• Time: O(n)
• Space: O(n)

---

💡 Optimized Approach 2: Two Pointers (Space O(1))

We use two pointers (left, right) and two variables (leftMax, rightMax) to simulate the process:

• Always move the pointer with lower height
• Update leftMax or rightMax and calculate trapped water accordingly

🔢 Java Code (Two Pointers)

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

        return total;
    }
}

⏱ Complexity

• Time: O(n)
• Space: O(1)

---

✍️ Summary

• This is a classic two-pointer technique problem with a space optimization.
• The intuition is that water is bounded by the shorter side.
• First solve using prefix arrays to build understanding, then optimize to two pointers.