Sign in
Skip to solution
hardDSA

How do you solve the trapping rain water problem?

818 views
01

Understand the problem

Explain water trapping.

arraystwo-pointers
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Water above each bar = min(maxLeft, maxRight) - height[i]. Use two pointers moving inward, tracking the running left/right maxima and adding trapped water on the smaller side. O(n) time, O(1) space — no need to precompute full max arrays.

Solution ready — 2 min read

Classified // press E to declassify

04

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
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 110 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track