The O(n) Club: Trapping Rain Water: Arrays, Puddles, and Other Unexpected Flood Zones

The O(n) Club: Trapping Rain Water—Arrays, Puddles, and Other Unexpected Flood Zones

⚡ TL;DR

Given a list of bar heights, your job is to calculate how much water these little fences can hold after a biblical downpour. The brute-force way checks every position’s left and right max—so slow, you’ll have mold before it finishes. There are smarter ways—dynamic programming with left/right arrays, or the two-pointer approach for the efficient (or lazy). Here’s a brute force Java taste:

// Brute force (bring coffee)
int trapped = 0;
for (int i = 1; i < height.length - 1; i++) {
    int leftMax = 0, rightMax = 0;
    for (int j = 0; j <= i; j++) leftMax = Math.max(leftMax, height[j]);
    for (int j = i; j < height.length; j++) rightMax = Math.max(rightMax, height[j]);
    trapped += Math.min(leftMax, rightMax) - height[i];
}

🧠 How Devs Usually Mess This Up

Classic blunder: people see the problem and go, “Easy! Water = highest-on-the-left or right minus current bar.” A beautiful recipe for negative water (antigravity puddles, anyone?). Or they try to juggle just a single max, missing the whole point of “which side is lower?” Even worse, some forget that if the min of left and right is lower than your bar you don’t get negative water—you get dust.

🔍 What’s Actually Going On

Imagine you line up bathtubs of varying heights; pour rain on everything. Each tub only holds as much water as the shorter wall on either end—the weak link. Wherever you are: Your waterline is the min of the highest wall to your left and right. Subtract your bar height, and that’s your puddle (or not). If you thought water just looks for the ground, congrats—you’ve reinvented a leaky sieve.

🛠️ PseudoCode

• Create two arrays: leftMax[] holds the tallest bar to your left (incl. you), rightMax[] does the same for the right.
• Fill them up:
  • Loop left to right to set leftMax[]
  • Loop right to left for rightMax[]
• For each bar (skip the first and last—unless you’re feeling generous):
  • Calculate Math.min(leftMax[i], rightMax[i]) - height[i]
  • If the answer’s negative, pretend it’s zero (unless you’re coding a Sahara simulator)
• Add ’em up.
• Or avoid arrays: Set left and right pointers, track leftMax/rightMax as you squeeze inward.

// Fancy DP arrays, Java revision
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]);

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge cases: All bars same height? Flat? Empty input? There’s not going to be a drop of water, and absolutely no drama.
• Negative water: If your math says negative, set it to zero. Otherwise, you’re draining oceans on Mars.
• Complexity check: Two-pointer method? O(n) time, O(1) space. DP array? O(n) time, O(n) space (more RAM for those who like to flex).

🧠 Interviewer Brain-Tattoo

“If you solve Trapping Rain Water without getting lost in a flood of nested loops or wasted arrays, you might actually enjoy writing production code.”