Trapping Rain Water 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

Given n non-negative integers representing an elevation map, compute how much water can be trapped after raining.

height = [0,1,0,2,1,0,1,3,2,1,2,1]
# Output: 6 units of water trapped

The water at each position = min(maxLeft, maxRight) - height[i]. We can compute this with two pointers:

Use left and right pointers starting from both ends
Track leftMax and rightMax
Move the pointer with the smaller max — water is bounded by the smaller side

This is a Hard problem — time: O(n), space: O(1). Don't worry if it takes multiple attempts!

📋 Instructions

Implement `trap(height)` using the two-pointer approach. Test with `height = [0,1,0,2,1,0,1,3,2,1,2,1]` and print the result.

Two pointers inward won't work here. Use a stack or dynamic approach. For each bar, the water above it = min(max_left, max_right) - height. Two-pointer from both ends tracking max.

🧪 Test Cases

Input

trap([0,1,0,2,1,0,1,3,2,1,2,1])

Expected

6

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›