Given the heights of a row of bars, work out how much rainwater is trapped between them. Do it in constant extra space.

Water at one index, before any pointers

Do not start with pointers. Start by working out how much water sits on top of a single bar, because every solution to this problem is the same formula evaluated in a different order.

Water above index i is held in place by the tallest bar somewhere to its left and the tallest bar somewhere to its right. The water level is the lower of those two maxima, since water spills over the shorter wall, and the water actually present is that level minus the bar's own height. If the bar is at least as tall as the lower maximum, the amount is zero rather than negative.

Take the heights 4, 2, 0, 3, 2, 5. The running maximum from the left, taken inclusively, is 4, 4, 4, 4, 4, 5. From the right it is 5, 5, 5, 5, 5, 5. Index by index, the smaller of the two minus the height gives 0, 2, 4, 1, 2, 0, so the total is 9. That is the whole answer, computed with no cleverness at all, and it is the thing every other version has to agree with.

Three orderings of the same formula

The direct implementation of that paragraph is two passes to build the prefix maximum and suffix maximum arrays and a third to sum. It is O of n in time and space, obviously correct, and the version to write first if space is unconstrained. The monotonic stack version computes the same thing by keeping indices of bars in decreasing height order and settling a basin whenever a taller bar arrives to close it; also O of n in both, and the one to reach for if the follow-up asks for water per basin.

The two-pointer version computes the same thing in O of 1 space, and it is what the constraint is asking for. It is worth understanding rather than memorising because the space saving comes from one specific observation about which of the two maxima you actually need to know.

Why advancing the shorter side is safe

Keep a pointer at each end and a running maximum for each side, covering only the bars each pointer has already passed. The claim is that when the left height is not greater than the right height, the water above the left pointer is fully determined by the left running maximum, even though you have not seen most of the array.

The argument is short. Water above the left pointer is the smaller of its true left maximum and its true right maximum, minus its height. The left running maximum is already the true left maximum, because the left pointer has passed every bar to its left. The true right maximum is unknown but is at least the height at the right pointer, since that bar lies to the right. And the left running maximum is at least the left pointer's own height, which by assumption does not exceed the right pointer's height. So the left maximum is the smaller of the two and therefore the one setting the level, and whatever taller bars hide in the unexplored middle can only raise the right maximum, which changes nothing.

The reasoning is symmetric, so when the right height is smaller it fixes the water above the right pointer instead. Each step settles one index with certainty and moves inwards, and the array is consumed exactly once.

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

    while (left < right) {
        if (height[left] <= height[right]) {      // left maximum is the binding constraint
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];      // never negative: leftMax includes this bar
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

The reason no clamp at zero is needed is that the running maximum is updated to include the current bar before the subtraction, so the difference cannot go below zero. That is a small thing to get right and a common source of an off-by-one-bar overcount when the update and the subtraction are written in the other order.

Walking 4, 2, 0, 3, 2, 5

The pointers start at the 4 and the 5. The left height 4 does not exceed the right height 5, so the left side moves: leftMax becomes 4, and 4 minus 4 adds nothing. Left now sits on the 2; still not greater than 5, so leftMax stays 4 and 4 minus 2 adds 2. On the 0, that adds 4, taking the total to 6. On the 3, one more. On the 2, two more, reaching 9. The pointers have met, and 9 matches the index-by-index figure above.

Notice that the right pointer never moved, which happens whenever the tallest bar is at one end. It is a useful sanity case, because an implementation that advances both pointers every iteration, or compares against the running maxima instead of the current heights, gives a different number here.

The comparison at equality, and the degenerate inputs

When the two heights are equal, either branch is correct, and the argument above shows why: each running maximum is then no greater than the opposite side's guaranteed lower bound, so both indices are determined. Making the comparison inclusive on one side is a free choice; the only requirement is that some branch always advances a pointer.

Fewer than three bars hold nothing, and the loop handles that without a special case: with two bars the single iteration adds the running maximum minus the bar it just absorbed, which is zero. A monotonically increasing or decreasing array also yields zero, and it is worth checking one aloud, because it exposes an implementation that forgot water needs a wall on both sides.