The Runtime Theory
hardLeetCode#two-pointers#prefix-maxima

Trapping Rain Water

Compute how much water remains above each bar after rain, assuming equal-width bars.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

inheight=[0,1,0,2,1,0,1,3,2,1,2,1]

out6

inheight=[4,2,0,3,2,5]

out9

inheight=[]

out0

Compute how much water remains above each bar after rain, assuming equal-width bars.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain the time and space complexity in terms of the input sizes and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs covered by the contract.

Reasoning prompt

Relate water at an index to the lower of its left and right maximum boundaries. Compare prefix arrays with a constant-space two-pointer method.

Use the linked judge for the canonical problem. The examples above are compact TRT checks; write additional cases before submitting, especially for the boundary that tends to break your chosen invariant.

More practice in this topic

medium · two pointersContainer With Most Watermedium · two pointers3Summedium · two pointersTwo Sum II - Input Array Is Sorted

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save