Leetcode 42 — Trapping Rain Water

This article will cover and explain 2 solutions to Leetcode 42, Trapping Rain Water. There are concepts that overlap with Leetcode 11 (Container With Most Water), and I recommend solving that before tackling this.

Problem Overview

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

A question you may have is: Does a ‘container’ require two walls and a bottom? Answer: It requires two walls (i.e. the edges don’t fill) and does not need a bottom (i.e. the x-axis is the bottom of each ‘container’).

I think it’s best to walkthrough an example to understand.

Example

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

To get a more in depth understanding of how those positions contains water, I’ve made diagrams that call out index 1 :

This logic repeats for each position, and the total is accumulated to get the output

Strategy, Concepts, and Solution

For us to get the total amount of water captured, we first need to understand how water is captured. Similar to Container With Most Water, the amount of water that can be contained is an area that is bounded in height by the shortest wall on the left and right. However, in this problem the heights have widths and displace water, AND we need all the containers. With that being said, I think it’s useful to take a look at the example again:

We can break down this problem by evaluating the total amount of water each position in height(the input elevation map) can capture. We do this by finding the maximum height to the left and right of height[i] . Why? Because the minimum of those heights is the highest water can be captured (if it can be). Take index 1 from above; the highest water can be captured is 4 height units, any more and it overflows (is above the shortest wall).

Then, now that we know height[i]'s max height it can capture, we subtract that from height[i] to get the amount of water index iwill capture. So, looking at the above figure, height[i] = 2 and min(height left, height right) = 4 , we have water captured = 4 — 2 = 2 .

So, what does this look like as code? One way is to first capture the max heights to the left and right of each element:

From here, we just follow our equation to get the amount of water added per element in height

Notice here that I added the additional step of doing min(0, ...) because you could have a case where maxLefts[i] > maxRights[i] and maxLefts[i] == height[i] , so maxRights[i] — height[i] is negative.

Putting it all together it looks like this:

Which is O(n) time, and O(n) space. So, can we do better? What if we have a space constraint of O(1)? Here, we can use two pointers similar to Container With Most Water.

We’ll work from the outside in, with a left that starts at index 0 and right that starts at len(height)-1. Remember how we’re bounded by the minimum of the maximum walls to i's left and right? We’re going to continue to use that property but in a more efficient way.

There’s 5 things we need to track:

1. Max Height Observed on the left
2. Max Height Observed on the right
3. A left pointer
4. A right pointer
5. The answer

Our algorithm will have one loop, ensuring that our left and right don’t cross. We’ll increment left and right based on which is smaller. Why? It goes back to how the minimum wall height is what is the most restricting. If height[left] < height[right] then we know that the right side cannot be our restriction by definition. Next, we simply check if height[left] < max height observed on the left because if that is False (we observed a larger height) then we need to update our respective max height.

The two pointer solution then will read like so:

This is still O(n) time but now it is O(1) space.

Thanks for reading! I hope you enjoyed the article :))) !