Trapping Rain Water

Learning goal: Recognize what determines the water level above each bar.

Core idea For an index i, water is bounded by the tallest wall anywhere to its left and the tallest wall anywhere to its right. The water level is the smaller of those two wall heights. After subtracting height[i], any positive remainder is trapped water.

Algorithm plan

• Identify the left and right boundaries of the array.
• Reason about the best wall seen from each side.
• Add only positive contributions above the current bar.

Micro-example For [3,1,2], the middle bar sees left maximum 3 and right maximum 2. Its water level is min(3,2) = 2, so it traps 2 - 1 = 1 unit.

Pitfalls

• A bar at an edge cannot trap water because one side has no wall.
• The taller wall does not determine the current amount by itself; the shorter side is the bottleneck.
• Never add a negative amount when a bar reaches or exceeds its boundary.

Recap

• Water depends on the smaller tallest wall on the two sides.
• Each bar contributes independently once those boundaries are known.
• The two-pointer method maintains these boundaries without building arrays.

Learning goal: Understand why one side can be processed safely before the other.

Core idea Keep pointers left and right, plus leftMax and rightMax, the tallest bars encountered so far from each side. If leftMax <= rightMax, the left side is the bottleneck: regardless of what lies farther right, the right boundary is at least rightMax, so the left bar's contribution is determined by leftMax. The symmetric argument applies when rightMax < leftMax.

Data structure model

Micro-example If leftMax = 2 and rightMax = 5, process left. A left bar of height 1 adds 2 - 1 = 1, then left advances.

Pitfalls

• Comparing current bar heights instead of leftMax and rightMax loses the running-boundary invariant.
• Advancing both pointers can skip bars whose contribution is not yet safe.
• Update the relevant maximum before calculating that side's trapped water.

Recap

• Maintain maxima incrementally.
• Process the smaller maximum because it is the bottleneck.
• Each pointer moves inward once, producing a linear scan.

Learning goal: Translate the bottleneck argument into a one-pass algorithm.

Core idea At every iteration, the unprocessed region lies between left and right. If leftMax <= rightMax, the current left bar has a guaranteed right boundary of at least rightMax, so its water is exactly leftMax - height[left] after updating leftMax. We can process it permanently and move inward. This preserves the invariant that every added amount is final.

Algorithm plan

1. Set left = 0, right = n - 1, and both running maxima to 0.
2. While left <= right, compare leftMax and rightMax.
3. Process the side with the smaller maximum.
4. Update that maximum, add its difference from the current bar, and advance the pointer.

while left <= right:
    if left_max <= right_max:
        left_max = max(left_max, height[left])
        answer += left_max - height[left]
        left += 1
    else:
        right_max = max(right_max, height[right])
        answer += right_max - height[right]
        right -= 1

Micro-example With leftMax = 2 and rightMax = 3, a left bar of height 0 contributes 2. The right side is already tall enough that no future discovery can lower this left-side level.

Pitfalls

• Use <= consistently in one branch; equality is safe for either side.
• Do not separately scan for maxima inside the loop.
• Updating a maximum and adding max - height naturally gives zero for a new tallest bar.

Recap

• One pointer advances per iteration.
• The invariant makes each contribution final when added.
• The algorithm uses constant auxiliary space.

Learning goal: Trace every pointer decision on a complete input.

Core idea We use height = [0,1,0,2,1,0,1,3,2,1,2,1], which has answer 6. The pointers begin at both ends. The side with the smaller running maximum is processed, so the trace may move left several times and then right several times as the bottleneck changes.

Algorithm plan

• Track left, right, leftMax, rightMax, and answer.
• When processing left, update leftMax and add leftMax - height[left].
• When processing right, update rightMax and add rightMax - height[right].
• Stop after the pointers meet.

Micro-example At index 2, leftMax = 1 and height[2] = 0, so one unit is added. Later, index 5 sees leftMax = 2, contributing two units; these are part of the final six.

Pitfalls

• The pointer position is not the same as the running maximum.
• A zero contribution is still a meaningful step: it confirms a boundary bar.
• Keep the running total visible to avoid losing contributions across direction changes.

Recap

• Left processing contributes at indices 2, 4, 5, 6, and 8.
• The total becomes 1 + 1 + 2 + 1 + 1 = 6.
• The next widget exposes each state transition.

Learning goal: Avoid the implementation mistake that destroys the linear-time guarantee.

Core idea A tempting solution scans leftward and rightward from every index to recompute the tallest walls. Although the formula is correct, repeating those scans costs O(n²). The two-pointer solution maintains the maxima incrementally, so each bar is examined once.

Algorithm plan

• Initialize both maxima to 0, which handles edge bars and zero-height input naturally.
• Advance exactly one pointer on each loop iteration.
• Use max(currentMax, height[index]) before adding water.
• Test empty, short, monotonic, and flat arrays.

Micro-example For [1,2,3], the running maxima rise with every bar, so the answer is 0. For [3,2,1], the right maximum rises while processing from the right, also giving 0.

Pitfalls

• Forgetting to update the maximum before subtraction can produce negative water.
• Moving both pointers in one iteration can skip an unresolved bar.
• Arrays with fewer than three bars always trap zero water.
• The monotonic stack alternative uses O(n) space; it is not the target approach here.

Recap

• Incremental state prevents repeated work.
• Monotonic or flat terrain is handled without special-case branches.
• Check pointer movement and maximum updates carefully.

Learning goal: Explain why the two-pointer solution meets the target bounds.

Core idea Each loop iteration advances left or decreases right; neither pointer ever moves backward. Therefore, there are at most n pointer advances and a constant amount of work per advance. The algorithm stores only a few scalar variables, unlike prefix/suffix arrays or a monotonic stack.

Algorithm plan

• Count each bar as processed once.
• Treat maximum updates, comparisons, and additions as constant-time operations.
• Report auxiliary space separately from the input array.

Micro-example For n = 12, the walkthrough makes at most 12 pointer advances and returns 6. Doubling n roughly doubles the work rather than quadrupling it.

Pitfalls

• Do not report O(n) space for the input array when discussing auxiliary space.
• A monotonic stack is linear time but uses O(n) additional space.
• The repeated-maxima approach has the right answer but misses the required performance target.

Recap

• Time: O(n).
• Auxiliary space: O(1).
• The canonical strategy is two pointers; the monotonic stack is a useful alternative perspective.