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.
nnon-negative integers representing an elevation map where the width of each bar is
1, compute how much water it can trap after raining.
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.
Input: height = [4, 2, 0, 3, 2, 5]
To get a more in depth understanding of how those positions contains water, I’ve made diagrams that call out index
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
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
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:
Max Height Observed on the left
Max Height Observed on the right
A left pointer
A right pointer
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 :))) !