Problem

Read the prompt, flip through the examples, then steal the idea.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Constraints

—n == height.length
—1 <= n <= 2 * 10^4
—0 <= height[i] <= 10^5

Examples

Input

height =: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output

6

elevation map

6 units of rain water (shaded) are trapped between the bars.

02

Solution

3 approaches · Python and Go. Pick a tab — the walkthrough follows.

Optimal▶ Animated

Always settle the column under the shorter wall — its water level is already fully determined.

Whichever side is currently shorter has a taller bar waiting on the other side, so its water level equals its own running maximum. Add that column's water, advance that pointer, repeat.

Algorithm

l = 0, r = n − 1, leftMax = rightMax = 0, water = 0.
While l < r: if height[l] < height[r]: leftMax = max(leftMax, height[l]), water += leftMax − height[l], l += 1.
Else: rightMax = max(rightMax, height[r]), water += rightMax − height[r], r −= 1.
Return water.

Time: O(n)
Space: O(1)

Solution.py

1class Solution:2    def trap(self, height: list[int]) -> int:3        l, r = 0, len(height) - 14        left_max = right_max = 05        water = 06        while l < r:7            if height[l] < height[r]:8                # a taller wall exists on the right, so left_max decides the level here9                left_max = max(left_max, height[l])10                water += left_max - height[l]11                l += 112            else:13                right_max = max(right_max, height[r])14                water += right_max - height[r]15                r -= 116        return water

Watch this run

03

Interactive walkthrough

Playing “Two pointers, O(1) space”. Edit the input, hit Run, then scrub.

Approach: Two pointers, O(1) space

Loading animation…

Trapping Rain Water