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

The key insight is to think about water on a per-bar basis rather than trying to figure out entire pools at once. For any single bar at index i, the water above it is determined by the tallest bars to its left and right. Water rises to the level of the shorter of those two tallest bars (because it would spill over the shorter side), and then you subtract the bar's own height.

So the formula for 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 this value is negative (the bar is taller than the surrounding walls), no water sits above it, so the contribution is 0.

Every approach to this problem is just a different way of computing maxLeft and maxRight efficiently.

Key Constraints:

Intuition

The most direct approach: for each bar, look left and right to find the tallest walls on each side. The water above that bar is min(maxLeft, maxRight) - height[i].

This is essentially computing the formula from the "Understanding the Problem" section in the most literal way possible. For each index, we scan the entire array to the left and right to find the maximums.

Algorithm

Example Walkthrough

Code

The brute force recomputes the left and right maximums from scratch for every bar, which is redundant. What if we precomputed those maximums in a single pass each?

Intuition

The brute force recomputes maxLeft and maxRight from scratch for every index. But notice that maxLeft[i] only depends on maxLeft[i-1] and height[i]. The same goes for maxRight from the other direction. So we can build both arrays in a single pass each, then compute the water in a third pass.

This is a classic dynamic programming technique: precompute prefix and suffix maximums, then combine them.

Algorithm

Example Walkthrough

Code

The prefix max approach gets us to O(n) time, but we're using O(n) extra space for two arrays. Can we compute the water without storing all the prefix maximums, using only constant space?

Intuition

Here's the clever observation that makes O(1) space possible: at any position, the water is determined by min(maxLeft, maxRight) - height[i]. We don't actually need to know both max values precisely. We only need to know the smaller one, because that's the bottleneck.

Imagine two pointers, one at each end of the array, moving inward. We also track leftMax (the tallest bar seen from the left so far) and rightMax (the tallest bar seen from the right so far).

If leftMax < rightMax, we know for sure that the water at the left pointer is constrained by leftMax, regardless of what rightMax actually is. Why? Because the true right max for the left pointer is at least rightMax (there could be taller bars between the right pointer and the left pointer), so min(leftMax, trueRightMax) = leftMax. We can safely compute the water at the left pointer and advance it.

The same logic applies symmetrically: if rightMax <= leftMax, the water at the right pointer is constrained by rightMax.

Algorithm

Example Walkthrough

Code