pytudes._2021.leetcode.hard._42__trapping_rain_water

https://leetcode.com/problems/trapping-rain-water/

Examples:

>>> Solution().trap([])
0

See Also:

• pytudes/_2021/leetcode/blind_75/array/_11__container_with_most_water__medium.py

Module Contents

Classes

Solution

Functions

compute_trapped_rain_water(heights)

Given n non-negative integers representing an elevation map (height)

class pytudes._2021.leetcode.hard._42__trapping_rain_water.Solution

static trap(height)

Parameters:

height (list[int]) –

Return type:

int

pytudes._2021.leetcode.hard._42__trapping_rain_water.compute_trapped_rain_water(heights)

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

Notes:

if left_max_height and right_max_height are the maximum heights of the already-processed left and right elevations, respectively:

For each index i:

Since the amount of water we can trap is bounded by:

min(left_max_height, right_max_height)

and since no water can be trapped in space already taken up by:

heights[i]

this means that we trap exactly:

min(left_max_height, right_max_height) - heights[i] water.

heights = 2,0,1,0,3,1,0,2,2,0,4

[]

[] []

[] [] [][] [] []__[]__[][]__[][]__[] 0|2|1|2|0|1|2|1|1|2|0 = trapped_rain_water_at_each_idx => sum(trapped_rain_water_at_each_idx) = trapped_rain_water

Args:

heights: list of non-negative integers [a1, a2, …, an],

where each represents a point at coordinate (i, ai) i.e., the height of a vertical line at y-coordinate i is ai

Returns: Sum of areas between heights unbroken

Examples:

>>> compute_trapped_rain_water(heights=[0,1,0,2,1,0,1,3,2,1,2,1])
6
>>> compute_trapped_rain_water(heights=[4,2,0,3,2,5])
9
>>> compute_trapped_rain_water(heights=[1,0,1])
1
>>> compute_trapped_rain_water(heights=[1,1])
0
>>> compute_trapped_rain_water(heights=[1])
0
>>> compute_trapped_rain_water(heights=[])
0

Parameters:

heights (list[int]) –

Return type:

int