#42

Trapping Rain Water

expert · 1040 · lc hard +32 · verified · 66.9% accepted · 36,162 likes · top 73%

⚑ Prefix / Suffix Product ⚑ Converging Pointers (Pair / Triple Sum)⚑ Monotonic Stack

Description

A sequence of n non-negative integers represents an elevation map where each bar has width 1. Calculate the total units of rainwater that can be trapped between the bars.

Example 1:

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

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Code

1

2

3

class Solution:
    def trap(self, height: List[int]) -> int:

class Solution:
    def trap(self, height: List[int]) -> int: