Rain water trapping

To calculate how much rainwater can be trapped between bars, we use a two-pointer technique that runs in O(n) time and O(1) space.

Core Idea

Water trapped at any index depends on:
min(max height on left, max height on right) - current height
Instead of precomputing arrays, we walk inward from both ends, keeping track of:

leftMax → tallest bar seen from the left

rightMax → tallest bar seen from the right

const trapping = height => {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0, water = 0;

while (left < right) {
    if (height[left] < height[right]) {
        leftMax = Math.max(leftMax, height[left]);
        water += leftMax - height[left];
        left++;
    } else {
        rightMax = Math.max(rightMax, height[right]);
        water += rightMax - height[right];
        right--;
    }
}

return water;
}

1️⃣ Initialize pointers

left starts at beginning
right starts at end
leftMax and rightMax track the tallest bars seen so far
water stores total trapped water

2️⃣ Why compare height[left] < height[right]?

We always move the smaller height side because:
The trapped water is limited by the shorter boundary
If left bar is smaller → water depends on leftMax
If right bar is smaller → water depends on rightMax
This guarantees correctness without checking both sides every time.

3️⃣ When moving left pointer
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left++;

Update highest wall seen from left
Add water trapped at current index
Move inward

4️⃣ When moving right pointer
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;