Hard

Given a list height of non-negative integers, where each value is the height of a bar 1 unit wide, return how many units of rain water the bars trap after it rains. An empty list or a single bar traps 0.

`height`	result	why
`[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]`	`6`	three pools: 1 + 4 + 1
`[4, 2, 0, 3, 2, 5]`	`9`	one pool at level 4: 2 + 4 + 1 + 2
`[3, 0, 0]`	`0`	no wall on the right, nothing is held
`[]`	`0`	no bars

Water above bar $i$ cannot rise above the tallest bar to its left, nor above the tallest bar to its right — it spills over whichever of the two is lower. So the column at $i$ holds

\min(\text{maxL}_i, \text{maxR}_i) - h_i

where $\text{maxL}_i$ is the tallest bar in height[0..i] and $\text{maxR}_i$ the tallest in height[i..] (both ranges include bar $i$ , so the difference is never negative). Precomputing both as prefix and suffix arrays gives $O(n)$ time and $O(n)$ space; the two-pointer version drops the arrays.

Keep left and right pointers plus running maxima max_left (tallest bar in height[0..left]) and max_right (tallest in height[right..]).

```mempro-diagram { "version": 1, "kind": "array", "label": "height", "values": [4, 2, 0, 3, 2, 5], "caption": "The lower running maximum determines which side can be settled", "steps": [ { "caption": "max_left = 4 and max_right = 5, so settle the left edge and advance left.", "marks": [ { "role": "current", "cells": [0], "label": "Side being settled" }, { "role": "candidate", "cells": [5], "label": "Opposite boundary" } ], "pointers": [ { "label": "left", "at": 0 }, { "label": "right", "at": 5 } ] }, { "caption": "At index 1, the left wall is still 4; bar 2 traps 4 - 2 = 2 units.", "marks": [ { "role": "current", "cells": [1], "label": "Side being settled" }, { "role": "dependency", "cells": [0, 5], "label": "Known boundaries" } ], "pointers": [ { "label": "left", "at": 1 }, { "label": "right", "at": 5 } ] }, { "caption": "At index 2, the same boundaries prove that bar 0 traps 4 units; no right-side scan is needed.", "marks": [ { "role": "current", "cells": [2], "label": "Side being settled" }, { "role": "result", "cells": [1, 2], "label": "Settled water columns" } ], "pointers": [ { "label": "left", "at": 2 }, { "label": "right", "at": 5 } ] } ] } ```

Invariant: if max_left <= max_right, then the true right-side maximum for position left is at least max_right, hence at least max_left — so the water at left is exactly max_left - height[left], computable without ever scanning further right. Add it and advance left. Otherwise the mirror argument settles right: its water is max_right - height[right], then retreat right.

Each step retires one index, so the loop runs $O(n)$ with $O(1)$ extra space. The index where the pointers finally meet is at least as tall as the lower of the two walls, so stopping at left < right loses nothing.

Python

def trap(height):
    """Return the total units of rain water trapped between the bars of
    height (a list of non-negative ints, each bar 1 unit wide).
    An empty list or a single bar traps 0."""
    left, right = 0, len(height) - 1
    max_left = max_right = 0  # tallest bar in height[..left] / height[right..]
    water = 0
    while left < right:
        max_left = max(max_left, height[left])
        max_right = max(max_right, height[right])
        if max_left <= max_right:
            # Every bar right of `left` is capped by a wall of at least max_right
            # >= max_left, so the water level at `left` is exactly max_left.
            water += max_left - height[left]
            left += 1
        else:
            # Symmetric: the wall left of `right` is at least max_left > max_right,
            # so the water level at `right` is exactly max_right.
            water += max_right - height[right]
            right -= 1
    return water

Trapping Rain Water

Minimum Window Substring