Trapping Rain Water

The Goal

You get an elevation map as an array of n non-negative bar heights, one bar per index and each bar one unit wide. Work out the total amount of rain water that stays trapped between the bars.

Imagine looking at the side profile of a structure built with blocks. When it rains, water fills the "valleys" formed between taller "peaks".

Key Insight

For any given bar at index i, the amount of water it can hold above it is determined by:
min(max_height_to_left, max_height_to_right) - height[i]

If this value is negative, it means the bar is taller than the water level, so it holds 0 water.

The Two Pointer Approach

Instead of pre-computing the max height to the left and right for every index (which takes O(n) space), we can use two pointers to solve this in O(n) time and O(1) space.

1. Initialize left = 0 and right = n - 1.
2. Track leftMax and rightMax seen so far.
3. The Logic: The amount of water trapped at a position is limited by the shorter of the two boundaries.
   • If leftMax < rightMax: We know the water level at the left pointer is determined by leftMax (because there's a taller wall somewhere on the right). We move left forward, update leftMax, then add leftMax - height[left]. Updating first means a new tallest bar adds 0 rather than a negative amount.
   • If leftMax >= rightMax: We know the water level at the right pointer is determined by rightMax (because there's a taller wall somewhere on the left). We move right backward, update rightMax, then add rightMax - height[right].

Observe how the pointers move inward. The pointer on the side with the smaller max height moves, accumulating water as it goes.