HARD

Trapping Rain Water

Given n non-negative integers height representing an elevation map where each bar has width 1, compute how much water it can trap after it rains.

Example

Input height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output 6

Key Pointers

Water trapped above index i is min(max height to its left, max height to its right) - height[i] — the smaller of the two boundary walls decides how high the water can sit.
Two pointers closing inward let you track a running left-max and right-max without a second array — whichever side currently has the smaller max is the side whose water level is already fully determined.
Always move the pointer on the side with the smaller max: that side's contribution is knowable right now, while the other side still might get a taller wall later.

Step-by-Step Analysis

Set left = 0, right = len(height) - 1, left_max = 0, right_max = 0, water = 0.
While left < right: if height[left] < height[right], update left_max = max(left_max, height[left]), add left_max - height[left] to water, then advance left.
Otherwise, update right_max = max(right_max, height[right]), add right_max - height[right] to water, then pull right back.
Repeat until the pointers meet; return water.

Complexity

Time: O(n) — Space: O(1)

Code

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

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

    return water

Code Explanation

How the solution above works, piece by piece.

Pointers at both ends, plus left_max and right_max: the tallest wall seen so far from each side.
if height[left] < height[right]: the left side is lower, so the water over left depends only on left_max. A wall at least as tall as height[right] is guaranteed on the right.
Update left_max, add left_max - height[left] (0 if this bar is the new max) and move left right.
Otherwise do the mirror image on the right side.
Every bar is processed once: O(n) time and O(1) space, versus O(n) space for precomputed left-max/right-max arrays.

Visual Walkthrough

Running it on height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

Blue dashed blocks are water. Each column holds water up to the lower of the tallest walls on its left and right. The two-pointer code gets the same total without storing those maxima: it always works on the side whose wall is lower, because that side's max is the limiting one.

trapped water

Video Explanation

NeetCode — LeetCode 42