MANG Problem #1: Trapping Rain Water (Hard)

1. 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: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

2. Approach: From Brute to Optimized

flowchart LR
    Start([Start]) --> Pointers[Initialize Left=0, Right=N-1]
    Pointers --> Loop{Left < Right?}
    Loop -- No --> End([End])
    Loop -- Yes --> Check{H[L] < H[R]?}
    Check -- Yes --> LMax{H[L] >= LMax?}
    Check -- No --> RMax{H[R] >= RMax?}
    LMax -- Yes --> SetLMax[Update LMax] --> IncL[Left++]
    LMax -- No --> AddL[Total += LMax - H[L]] --> IncL
    RMax -- Yes --> SetRMax[Update RMax] --> DecR[Right--]
    RMax -- No --> AddR[Total += RMax - H[R]] --> DecR
    IncL --> Loop
    DecR --> Loop

The Brute Force (O(n²))

For every bar, look left to find the max height, look right to find the max height. The water trapped at the current bar is min(maxLeft, maxRight) - currentHeight.

Why it fails: Repeatedly scanning left and right for every index is too slow for large inputs.

The Optimized Pattern: Two Pointers (O(n))

Instead of pre-calculating max heights, we can use two pointers moving toward each other.

The amount of water is limited by the shorter side.
If leftMax < rightMax, we know for a fact that the water level at the left pointer is determined by leftMax.

3. Java Implementation

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

    while (left < right) {
        if (height[left] < height[right]) {
            // Left side is smaller, water depends on leftMax
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                totalWater += leftMax - height[left];
            }
            left++;
        } else {
            // Right side is smaller, water depends on rightMax
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                totalWater += rightMax - height[right];
            }
            right--;
        }
    }
    return totalWater;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Imagine a single bar. The only way it can hold water is if there is a "wall" on both its left and right that is taller than itself.
The Constraint: The height of the water is determined by the shorter of the two walls.
The Strategy: We start with pointers at the extreme ends. We always process the bar pointing to the shorter side, because that side's "max height" is the bottleneck for water.
Dry Run:
- [0,1,0,2,1,0,1,3,2,1,2,1]
- L=0, R=11. height[L] < height[R] (0 < 1). leftMax becomes 0.
- L=1, R=11. height[L] == height[R] (1 == 1). rightMax becomes 1.
- L=1, R=10. height[L] < height[R] (1 < 2). leftMax becomes 1.
- ... and so on, accumulating water whenever currentHeight < maxBoundary.

5. Edge Cases

Array size < 3: Zero water can be trapped.
Descending/Ascending only: No "valleys," so zero water.
All bars same height: Zero water.

6. Interview Discussion

Interviewer: "Can we do this in one pass?"
You: "Yes, using the two-pointer approach I just implemented. It avoids the O(n) space required by the pre-calculation (DP) approach while maintaining O(n) time."
Interviewer: "What if the width of bars was different?"
You: "I would multiply the trapped height by the width of each specific index."