Hard

Trapping Rain Water

092

Given non-negative integers representing an elevation map with unit-width bars, return the total units of rain water trapped after raining.

EXAMPLES

Example 1

Input
{
  "height": [
    0,
    1,
    0,
    2,
    1,
    0,
    1,
    3,
    2,
    1,
    2,
    1
  ]
}

Output
6

FUNCTION SHAPE

height: intArray→int

SOLUTION NOTE

This is a very similar idea to container with most water. We realize that essentially we want to maximize diff = min(max_prefix_height(i), max_suffix_height(i)) - height[i] for each i individually, and sum them for all i.

Note that depending on how we define prefix(i) (either as inclusive of i or exclusive), we will need a max(0, diff). (think about why, if it is exclusive then the diff can be negative, which obviously doesn't make sense.)

We can brute force this in O(n^2) time and O(1) space. We can use prefix max and suffix max dp to do this in O(n) time and space. But the optimal solution of O(n) time and O(1) space requires a greedy two pointers strategy.

If we have two pointers l,r if max_prefix_height[l] < max_suffix_height[r], we know that min(max_prefix_height(l), max_suffix_height(l)) = max_prefix_height[l]. Why? Because max_suffix_height(l) >= max_prefix_height_r(r). Think about that. So we can greedily compute for index l, and increment it. Similar logic for the else case.

Open on LeetCode ↗