The elevation map is a cross-section of terrain. When it rains, water fills the valleys between the bars. The question is how many units of water are trapped in total.

The cleanest way to count it is per bar rather than per pool. For any single bar at index i, the water sitting above it is bounded by the tallest bar to its left and the tallest bar to its right. Water rises only to the level of the shorter of those two walls, since it would spill over the shorter side, and then the bar's own height is subtracted.

So the water at position i is water[i] = min(maxLeft, maxRight) - height[i], where maxLeft is the tallest bar from index 0 to i and maxRight is the tallest bar from index i to n-1. If that value is negative (the bar is taller than the surrounding walls), no water sits above it and the contribution is 0.

Every approach below is a different way to compute maxLeft and maxRight efficiently, except the last one, which counts water in horizontal layers instead.

Key Constraints:

Intuition

For each bar, scan left and right to find the tallest wall on each side, then the water above that bar is min(maxLeft, maxRight) - height[i]. This applies the formula from above directly: for every index, scan the whole array to its left and to its right to find the two maximums.

Algorithm

Example Walkthrough

Code

Recomputing the left and right maximums from scratch for every bar repeats the same work. The next approach precomputes both in a single pass each.

Intuition

maxLeft[i] depends only on maxLeft[i-1] and height[i]: it is the larger of the two. The same recurrence runs in the other direction for maxRight. So both arrays can be built in a single pass each, after which the water at every index follows from a third pass. This is the prefix-and-suffix-maximum pattern: precompute the running maximums once, then combine them.

Algorithm

Example Walkthrough

Code

The prefix max approach reaches O(n) time but spends O(n) extra space on two arrays. The next approach removes those arrays and computes the water in constant space using two pointers.

Intuition

The water at a position is min(maxLeft, maxRight) - height[i], so only the smaller of the two maximums matters. The larger one never affects the result. That observation removes the need to store both maximum arrays.

Use two pointers, left and right, starting at the ends and moving inward, along with leftMax (the tallest bar seen from the left so far) and rightMax (the tallest bar seen from the right so far). Compare height[left] and height[right] to decide which side to process.

When height[left] < height[right], the left pointer's water depends only on leftMax. The water at left is min(leftMax, trueRightMax) - height[left], where trueRightMax is the actual tallest bar to the right of left. We never have to compute trueRightMax: the bar at right is itself to the right of left, so trueRightMax is at least height[right], which exceeds height[left]. Whenever water sits on left, the binding wall is leftMax (a value at least height[left]), and the right side already offers a wall taller than height[left], so the water level is set by leftMax. The water at left can be computed from leftMax alone, and left advances.

The symmetric case, height[right] <= height[left], constrains the right pointer's water by rightMax.

Algorithm

Example Walkthrough

Code

Intuition

The previous approaches count water vertically, one column at a time. A stack counts it horizontally instead, filling each trapped region as a flat slab between a left wall and a right wall.

Scan left to right and keep a stack of bar indices whose heights are non-increasing from bottom to top. When the current bar is taller than the bar on top of the stack, that top bar is a local dip with a wall on both sides: the new top of the stack on its left, and the current bar on its right. Pop the dip, and the water resting on it is a rectangle whose height is min(leftWall, rightWall) - dipHeight and whose width is the gap between the two walls. Add that slab and keep popping while the current bar stays taller than the new top.

This bounds each region by the shorter of its two walls, the same rule as before, but resolves a whole horizontal layer per pop rather than a single column.

Algorithm

Example Walkthrough

Code

The stack matches the two-pointer approach on time but uses O(n) space, so the two-pointer solution remains the best on space. The horizontal-slab technique it uses carries over to related problems where counting columns directly is harder to set up.