Trapping Rain Water

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Examples

The brute-force approach

For each position i, find the max height to its left and max height to its right. Water at position i = min(left_max, right_max) - height[i] (if positive).

total = 0
for i in range(n):
    left_max = max(height[:i+1])
    right_max = max(height[i:])
    total += max(0, min(left_max, right_max) - height[i])
return total

O(n²) — recomputing max from both sides for every position.

Spotting the pattern

This is a Two Pointers problem. The key question to ask yourself:

When height[left] < height[right], why is the water at the left pointer definitively leftMax - height[left], even though you haven't seen the full right side yet?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.