NUHMAN.com

📌 Problem Statement

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.

📉 Input Example

java

int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};

🌧 Expected Output:

6

🔍 Intuition Behind the Problem

Visualize bars of different heights as histogram pillars, where rainwater gets trapped in the "valleys" between them. The trapped water at any position is determined by the shorter of the tallest bars to the left and right minus the current height.

🚀 Optimal Approach: Two-Pointer Technique

🔑 Key Concepts:

• Use two pointers, one starting from the left and the other from the right.
• Track the maximum height seen so far from both sides: leftMax and rightMax.
• At each step:
• Move the pointer on the shorter side.
• Compute the water that can be trapped at that position based on the min height of the max boundaries.

🧠 Time & Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(1)

Efficient for large input arrays.

💻 Java Code Implementation

java

public class TrappingRainWater {

    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int trappedWater = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    trappedWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    trappedWater += rightMax - height[right];
                }
                right--;
            }
        }

        return trappedWater;
    }

    public static void main(String[] args) {
        TrappingRainWater solution = new TrappingRainWater();
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println("Trapped water: " + solution.trap(height)); // Output: 6
    }
}

🧪 Explanation of the Output

For the input {0,1,0,2,1,0,1,3,2,1,2,1}:

• Water is trapped at indices: 2, 4, 5, 6, 8, and 10.
• The total is 6 units of water.

🛠️ Real-World Applications

• Landscape modeling and simulation
• Reservoir and dam water level predictions
• Game development (physics engines)

🧵 Bonus: Naive vs. Optimal

ApproachTimeSpaceNotesBrute-forceO(n²)O(1)Scans left/right for every indexPrefix ArrayO(n)O(n)Uses extra space for prefix max arraysTwo-pointerO(n)O(1)Most efficient (used above) ✅

✅ Summary

• The two-pointer approach is the most efficient way to solve the trapping rainwater problem.
• It requires only one pass and uses constant space.
• Great example of how to optimize a solution by using clever pointer movement.