hardDSA

How do you solve the trapping rain water problem?

Q: How do you solve the trapping rain water problem?

**Intuition.** Water sitting above bar i is capped by the **shorter** of the tallest wall to its left and the tallest to its right, minus its own height. With two pointers you compute this in one pass: whichever side has the smaller running max is the side whose water you can safely finalise. water[i] = min(maxLeft, maxRight) − height[i] <rect x="92" y="110" wi

818 views

Understand the problem

Explain water trapping.

arraystwo-pointers

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Two-pointer water trapping

Run Playground

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = total = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            total += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            total += right_max - height[r]
            r -= 1
    return total


# --- demo ---
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))   # 6

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How does the Bellman-Ford algorithm work?

How do you solve the word ladder problem?