Trapped Rain Water

L10 Hard Two Pointers

Concept

Water collects above a column up to the lower of the tallest walls on its left and right. Precomputing or tracking those walls from both ends solves it in linear time.

Given an array of non-negative integers height where each value is a bar width of 1, return how many units of water can be trapped above the bars after it rains.

Examples

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

→ 6

▸ height = [4, 2, 0, 3, 2, 5]

→ 9

▸ height = [1]

→ 0

Progressive Hints

Hint 1 · Nudge

Water above a bar is capped by the shorter of the two tallest walls on its sides.

Hint 2 · Plan

For each column, the water is max(0, min(left highest, right highest) minus its own height). Precompute the highest on the left and right for every column and sum the results.

Hint 3 · Approach

Build a leftMax array and a rightMax array, then total up max(0, min(leftMax[i], rightMax[i]) - height[i]) across all columns.

Output

// Run your code to see the output here.