Trapping Rain Water

Compute the total water trapped between elevation bars using two-pointer technique.

array two-pointers water-trapping simulation

Write a function `trap(height)` that takes a list of non-negative integers `height` (each element is the height of a bar of width 1) and returns the total amount of water that can be trapped after raining.

**Details:**
- Each bar has width 1.
- Water is trapped between bars if there are higher bars on both sides.
- The function must handle empty lists and lists with fewer than 3 elements (return 0 in those cases).
- The input list may contain zeros.
- The function signature: `def trap(height: list) -> int:`

Constraints

Input length: 0 <= n <= 2 * 10^4
Each height: 0 <= height[i] <= 10^5
Expected time complexity: O(n) using two-pointer technique. Space complexity: O(1) (excluding input).
The input list is not modified.

Example

>>> trap([0,1,0,2,1,0,1,3,2,1,2,1])
6
>>> trap([4,2,0,3,2,5])
9
>>> trap([1,2,3,4])
0
>>> trap([])
0

40 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about how much water each bar can hold above it: it depends on the minimum of the maximum height to its left and right.

Use two pointers starting from both ends, moving the pointer with the smaller height inward.

Keep track of the left_max and right_max as you move.

When the current bar is lower than the max on that side, it can trap water equal to that max minus current height.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.