Trapping Rain Water problem and solution in Java and Python

Let’s break down the Trapping Rain Water problem step-by-step — from the kid version to the optimized code.

---

🧩 Problem Statement

You are given an array height[] representing the height of bars (buildings). When it rains, water gets trapped between the bars. You must calculate how much water can be trapped in total.

---

💡 Example

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

Visualization:

        #
    #~~~##~#
#~~~##~##~##
-------------
 4  2  0  3  2  5

→ 9 units of water are trapped between the bars.

---

🧒 Explained to a Kid

Imagine a line of walls (like blocks of Lego). When it rains, water fills up the gaps between taller walls.

• If both sides are tall, the middle fills up with water.
• If one side is short, water leaks out from that side.

We must calculate how much water sits on top of each block.

---

🧠 Intuition

For each position i, 👉 the water trapped = min(max_left, max_right) - height[i]

Where:

• max_left = tallest bar on the left of i
• max_right = tallest bar on the right of i

If either side has no taller bar, no water is trapped there.

---

🐢 Brute Force Approach

For each index:

1. Look left → find max height
2. Look right → find max height
3. Water = min(left_max, right_max) - height[i]

⏱️ Time: O(n²)

🧠 Space: O(1)

---

⚡ Optimized Approach 1 — Precompute Left/Right Max Arrays

Steps:

1. Precompute:

   • left_max[i] = max height to the left of i
   • right_max[i] = max height to the right of i

2. Then for each bar:

   • water[i] = min(left_max[i], right_max[i]) - height[i]

✅ Time: O(n)

✅ Space: O(n)

---

💻 Java Implementation (Precomputed Arrays)

public class TrappingRainWater {
    public static 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 trapped = 0;
        for (int i = 0; i < n; i++)
            trapped += Math.min(leftMax[i], rightMax[i]) - height[i];

        return trapped;
    }

    public static void main(String[] args) {
        int[] height = {4, 2, 0, 3, 2, 5};
        System.out.println(trap(height)); // Output: 9
    }
}

---

💻 Python Implementation (Precomputed Arrays)

def trap(height):
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    trapped = 0
    for i in range(n):
        trapped += min(left_max[i], right_max[i]) - height[i]

    return trapped

print(trap([4, 2, 0, 3, 2, 5]))  # Output: 9

---

🧮 Optimized Approach 2 — Two Pointer Technique (O(1) Space)

Idea

We can avoid using extra arrays by using two pointers.

• Start with left = 0 and right = n-1

• Keep track of left_max and right_max

• Move the smaller side pointer inward:

  • If height[left] < height[right]:

    • If height[left] >= left_max, update left_max
    • Else, add water (left_max - height[left])
    • Move left++

  • Else:

    • Same logic for right

---

💻 Java Implementation (Two Pointer)

public class TrappingRainWaterTwoPointer {
    public static int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, trapped = 0;

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

    public static void main(String[] args) {
        int[] height = {4, 2, 0, 3, 2, 5};
        System.out.println(trap(height)); // Output: 9
    }
}

---

💻 Python Implementation (Two Pointer)

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = trapped = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                trapped += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                trapped += right_max - height[right]
            right -= 1

    return trapped

print(trap([4, 2, 0, 3, 2, 5]))  # Output: 9

---

🧠 Time and Space Complexity

Approach	Time	Space	Explanation
Brute Force	O(n²)	O(1)	Check each bar separately
Precomputed Arrays	O(n)	O(n)	Store left/right max arrays
Two Pointer	O(n)	O(1)	Best — no extra arrays

---

💧 Visual Analogy

Think of each bar as a wall in a city after rainfall. Water accumulates where both sides have taller walls. The two-pointer method walks from both sides toward the middle, keeping track of the highest walls seen so far — just like measuring puddles as you walk along a path after rain.

---