← Pointer Manipulation

Micro-Drill #124 — Trapping rain water

Pointer Manipulation Target: 15s

Two-pointer with running left/right max computes trapped water in O(n).

l, r = 0, len(h)-1
lm = rm = res = 0
while l < r:
    if h[l] < h[r]:
        lm = max(lm, h[l])
        res += lm - h[l]
        l += 1
    else:
        rm = max(rm, h[r])
        res += rm - h[r]
        r -= 1

Type it from memory. Go.

Practice Problems

• 42. Trapping Rain Water
• 11. Container With Most Water

Related Coding Drills

• Drill #124 — Trapping Rain Water Hard
• Drill #123 — Container With Most Water Medium