Trapping Rain Water: the idea to remember.

The core insight

Maintain maxima from both sides and process the side with the smaller maximum.

Why it works

If leftMax is smaller, a right boundary at least that tall is known, so water at the left position is determined. The argument is symmetric on the right.

The mistake to avoid

Water is determined by the smaller boundary maximum, not by the taller current bar.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int trap(int[] height) {
    int l = 0, r = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (l <= r) {
        if (leftMax <= rightMax) {
            leftMax = Math.max(leftMax, height[l]);
            water += leftMax - height[l++];
        } else {
            rightMax = Math.max(rightMax, height[r]);
            water += rightMax - height[r--];
        }
    }
    return water;
}

Make the next connection