Typorithm · hard

Trapping Rain Water

trapping-rain-watertwo-pointersconvergingrunning-maxbounded-side

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Trapping Rain Water

Two Pointers

Two pointers move inward from the lower side; trapped water at each bar is its running max minus its height.

Water above a bar is bounded by the shorter of the tallest walls to its left and right.

Moving from whichever side is currently lower guarantees that side's running max is the true bound.

Each step adds the gap between the running max and the current bar's height.

Process the lower side each step.

Running max bounds the water.

Add runningMax minus height per bar.

function trap(height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left += 1;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right -= 1;
    }
  }

  return water;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Running walls

Track the tallest wall seen from each side.

let leftMax = 0;
  let rightMax = 0

2. Work the lower side

The lower wall bounds the water, so process that side.

if (height[left] < height[right]) {

3. Add trapped water

Water above a bar is its left max minus its own height.

water += leftMax - height[left]

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.