How to Efficiently Solve the Trapping Rain Water Problem
Info
English content is still improving...
You will not only learn the algorithm tricks, also resolve these LeetCode problems:
LeetCode | Difficulty |
---|---|
11. Container With Most Water | 🟠 |
42. Trapping Rain Water | 🔴 |
Prerequisites
Before reading this article, you should first learn:
LeetCode problem #42 "Trapping Rain Water" is quite interesting and frequently appears in interviews. This article will walk you through step-by-step optimizations to solve this problem.
First, let's look at the problem:
42. Trapping Rain Water | LeetCode |
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.
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
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
The problem involves using an array to represent a bar chart and asks how much water this bar chart can trap at most.
int trap(int[] height);
int trap(vector<int>& height);
def trap(height: List[int]) -> int:
func trap(height []int) int {}
var trap = function(height) {}
Now let's introduce the brute-force solution -> memoization solution -> two-pointer solution step by step, solving this problem in O(N) time and O(1) space.
Core Idea
Small Tip
When tackling algorithm problems, if you have no idea where to start, try simplifying the problem. Begin with local considerations and write the simplest, most straightforward solution first. This might lead to a breakthrough. Gradual optimization may then reveal the optimal solution.
For example, in this problem, instead of considering how much water the entire histogram can hold, focus on how much water can be held at position i
.
It can hold 2 units of water because the height at height[i]
is 0, and the maximum water that can be held there is 2 units, calculated as 2-0=2.
Why can position i
hold a maximum of 2 units of water? It is because the water level at position i
is determined by the highest bars to its left and right, which we call l_max
and r_max
respectively. The maximum height of the water level at position i
is min(l_max, r_max)
.
In other words, the amount of water that can be held at position i
is:
water[i] = min(
# the highest pillar on the left
max(height[0..i]),
# the highest pillar on the right
max(height[i..end])
) - height[i]
This is the core idea of this problem. We can write a simple brute-force algorithm:
class Solution {
public int trap(int[] height) {
int n = height.length;
int res = 0;
for (int i = 1; i < n - 1; i++) {
int l_max = 0, r_max = 0;
// find the tallest pillar on the right
for (int j = i; j < n; j++)
r_max = Math.max(r_max, height[j]);
// find the tallest pillar on the left
for (int j = i; j >= 0; j--)
l_max = Math.max(l_max, height[j]);
// if itself is the tallest,
// l_max == r_max == height[i]
res += Math.min(l_max, r_max) - height[i];
}
return res;
}
}
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int res = 0;
for (int i = 1; i < n - 1; i++) {
int l_max = 0, r_max = 0;
// find the tallest pillar on the right
for (int j = i; j < n; j++)
r_max = max(r_max, height[j]);
// find the tallest pillar on the left
for (int j = i; j >= 0; j--)
l_max = max(l_max, height[j]);
// if itself is the highest,
// l_max == r_max == height[i]
res += min(l_max, r_max) - height[i];
}
return res;
}
};
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
res = 0
for i in range(1, n - 1):
l_max, r_max = 0, 0
# find the highest pillar on the right
for j in range(i, n):
r_max = max(r_max, height[j])
# find the highest pillar on the left
for j in range(i, -1, -1):
l_max = max(l_max, height[j])
# if itself is the highest,
# l_max == r_max == height[i]
res += min(l_max, r_max) - height[i]
return res
func trap(height []int) int {
n := len(height)
res := 0
for i := 1; i < n - 1; i++ {
l_max := 0
r_max := 0
// find the tallest pillar on the right
for j := i; j < n; j++ {
r_max = max(r_max, height[j])
}
// find the tallest pillar on the left
for j := i; j >= 0; j-- {
l_max = max(l_max, height[j])
}
// if itself is the highest,
// l_max == r_max == height[i]
res += min(l_max, r_max) - height[i]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
var trap = function(height) {
var n = height.length;
var res = 0;
for (var i = 1; i < n - 1; i++) {
var l_max = 0, r_max = 0;
// find the tallest pillar on the right
for (var j = i; j < n; j++)
r_max = Math.max(r_max, height[j]);
// find the tallest pillar on the left
for (var j = i; j >= 0; j--)
l_max = Math.max(l_max, height[j]);
// if itself is the tallest,
// l_max == r_max == height[i]
res += Math.min(l_max, r_max) - height[i];
}
return res;
};
This solution is straightforward but crude, with a time complexity of O(N^2) and a space complexity of O(1). However, it's clear that the way we calculate r_max
and l_max
is very clumsy, using a for loop to traverse every time. Can we optimize this process?
2. Memoization Optimization
In the previous brute-force solution, didn't we calculate r_max
and l_max
at every position i
? Let's precompute these results so we don't foolishly traverse every time, thus reducing the time complexity.
We create two arrays, r_max
and l_max
, to act as memoization. l_max[i]
represents the height of the tallest pillar to the left of position i
, and r_max[i]
represents the height of the tallest pillar to the right of position i
. By precomputing these two arrays, we avoid redundant calculations:
class Solution {
public int trap(int[] height) {
if (height.length == 0) {
return 0;
}
int n = height.length;
int res = 0;
// the array acts as a memo
int[] l_max = new int[n];
int[] r_max = new int[n];
// initialize the base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// calculate l_max from left to right
for (int i = 1; i < n; i++)
l_max[i] = Math.max(height[i], l_max[i - 1]);
// calculate r_max from right to left
for (int i = n - 2; i >= 0; i--)
r_max[i] = Math.max(height[i], r_max[i + 1]);
// calculate the answer
for (int i = 1; i < n - 1; i++)
res += Math.min(l_max[i], r_max[i]) - height[i];
return res;
}
}
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() == 0) {
return 0;
}
int n = height.size();
int res = 0;
// the array acts as a memo
vector<int> l_max(n);
vector<int> r_max(n);
// initialize the base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// calculate l_max from left to right
for (int i = 1; i < n; i++)
l_max[i] = max(height[i], l_max[i - 1]);
// calculate r_max from right to left
for (int i = n - 2; i >= 0; i--)
r_max[i] = max(height[i], r_max[i + 1]);
// calculate the answer
for (int i = 1; i < n - 1; i++)
res += min(l_max[i], r_max[i]) - height[i];
return res;
}
};
class Solution:
def trap(self, height: List[int]) -> int:
if len(height) == 0:
return 0
n = len(height)
res = 0
# array as a memo
l_max = [0] * n
r_max = [0] * n
# initialize the base case
l_max[0] = height[0]
r_max[n - 1] = height[n - 1]
# calculate l_max from left to right
for i in range(1, n):
l_max[i] = max(height[i], l_max[i - 1])
# calculate r_max from right to left
for i in range(n - 2, -1, -1):
r_max[i] = max(height[i], r_max[i + 1])
# calculate the answer
for i in range(1, n - 1):
res += min(l_max[i], r_max[i]) - height[i]
return res
func trap(height []int) int {
if len(height) == 0 {
return 0
}
n := len(height)
res := 0
// array as a memo
l_max := make([]int, n)
r_max := make([]int, n)
// initialize the base case
l_max[0] = height[0]
r_max[n-1] = height[n-1]
// calculate l_max from left to right
for i := 1; i < n; i++ {
l_max[i] = max(height[i], l_max[i-1])
}
// calculate r_max from right to left
for i := n-2; i >= 0; i-- {
r_max[i] = max(height[i], r_max[i+1])
}
// calculate the answer
for i := 1; i < n-1; i++ {
res += min(l_max[i], r_max[i]) - height[i]
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
var trap = function(height) {
if (height.length === 0) {
return 0;
}
var n = height.length;
var res = 0;
// the array acts as a memo
var l_max = new Array(n).fill(0);
var r_max = new Array(n).fill(0);
// initialize the base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// calculate l_max from left to right
for (var i = 1; i < n; i++) {
l_max[i] = Math.max(height[i], l_max[i - 1]);
}
// calculate r_max from right to left
for (var i = n - 2; i >= 0; i--) {
r_max[i] = Math.max(height[i], r_max[i + 1]);
}
// calculate the answer
for (var i = 1; i < n - 1; i++) {
res += Math.min(l_max[i], r_max[i]) - height[i];
}
return res;
};
This optimization is actually similar to the brute-force approach, but it avoids repeated calculations, reducing the time complexity to O(N), which is optimal. However, the space complexity is O(N). Let's look at a more elegant solution that can reduce the space complexity to O(1).
Three, Two-Pointer Solution
My Advice
This solution is for expanding your thinking; it's good to understand it, but you don't need to be overly obsessed with the optimal solution. For most people, in real interviews or exams, being able to use straightforward methods to tackle problems and write the above solution is sufficient. Although it adds some space complexity, it usually passes on most judging platforms.
Only if you can't pass all test cases and you have extra time after finishing other questions should you spend time optimizing the above solution.
The idea behind this solution is exactly the same, but the implementation is very clever. This time, we won't use a memo to pre-calculate; instead, we'll use two pointers to calculate on the go, saving space complexity.
First, let's look at a part of the code:
int trap(int[] height) {
int left = 0, right = height.length - 1;
int l_max = 0, r_max = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// At this point, what do l_max and r_max represent respectively?
left++; right--;
}
}
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int l_max = 0, r_max = 0;
while (left < right) {
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
// At this point, what do l_max and r_max represent respectively?
left++; right--;
}
}
def trap(height: List[int]) -> int:
left, right = 0, len(height) - 1
l_max, r_max = 0, 0
while left < right:
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
# At this point, what do l_max and r_max represent respectively?
left += 1
right -= 1
func trap(height []int) int {
left, right := 0, len(height) - 1
l_max, r_max := 0, 0
for left < right {
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
// At this point, what do l_max and r_max represent respectively?
left++
right--
}
}
var trap = function(height) {
var left = 0, right = height.length - 1;
var l_max = 0, r_max = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// At this point, what do l_max and r_max represent respectively?
left++; right--;
}
}
Regarding this section of the code, what do l_max
and r_max
represent?
It's quite straightforward: l_max
is the height of the tallest pillar in the range height[0..left]
, and r_max
is the height of the tallest pillar in the range height[right..end]
.
With this understanding, let's directly look at the solution:
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int l_max = 0, r_max = 0;
int res = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// res += min(l_max, r_max) - height[i]
if (l_max < r_max) {
res += l_max - height[left];
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
}
}
class Solution {
public:
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int l_max = 0, r_max = 0;
int res = 0;
while (left < right) {
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
// res += min(l_max, r_max) - height[i]
if (l_max < r_max) {
res += l_max - height[left];
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
}
};
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
l_max, r_max = 0, 0
res = 0
while left < right:
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
# res += min(l_max, r_max) - height[i]
if l_max < r_max:
res += l_max - height[left]
#<extend up -250>
#<div class="img-content"><img src="/images/接雨水/5.jpg" alt class="myimage" loading="lazy" photo-swipe="" /></div>
left += 1
else:
res += r_max - height[right]
right -= 1
return res
func trap(height []int) int {
left, right := 0, len(height) - 1
l_max, r_max := 0, 0
res := 0
for left < right {
l_max = max(l_max, height[left])
r_max = max(r_max, height[right])
// res += min(l_max, r_max) - height[i]
if l_max < r_max {
res += l_max - height[left]
left++
} else {
res += r_max - height[right]
right--
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
var trap = function(height) {
let left = 0, right = height.length - 1;
let l_max = 0, r_max = 0;
let res = 0;
while (left < right) {
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// res += min(l_max, r_max) - height[i]
if (l_max < r_max) {
res += l_max - height[left];
// See the image for a visual representation of the process
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
};
You see, the core idea here is exactly the same as before, just with minor differences in implementation. However, careful readers might notice some subtle differences:
In the previous memoization solution, l_max[i]
and r_max[i]
represent the highest bar in height[0..i]
and height[i..end]
respectively.
res += Math.min(l_max[i], r_max[i]) - height[i];
But in the two-pointer solution, l_max
and r_max
represent the highest bar in height[0..left]
and height[right..end]
respectively. For example, this piece of code:
if (l_max < r_max) {
res += l_max - height[left];
left++;
}
Here, l_max
is the highest bar to the left of the left
pointer, but r_max
is not necessarily the highest bar to the right of the left
pointer. Can this really give the correct answer?
Actually, we need to think about it this way: we only care about min(l_max, r_max)
. In the situation shown above, we already know l_max < r_max
, so whether this r_max
is the highest on the right doesn't matter. What matters is that the water that height[i]
can hold is only related to the difference with the lower l_max
:
In this way, the problem of trapping rainwater is solved.
Extension: Container With Most Water
Next, let's look at a problem very similar to the trapping rainwater problem, LeetCode Problem 11: "Container With Most Water":
11. Container With Most Water | LeetCode |
You are given an integer array height
of length n
. There are n
vertical lines drawn such that the two endpoints of the ith
line are (i, 0)
and (i, height[i])
.
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1] Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
// The function signature is as follows
int maxArea(int[] height);
// The function signature is as follows
int maxArea(vector<int> &height);
# The function signature is as follows
def maxArea(height: List[int]) -> int:
// The function signature is as follows
func maxArea(height []int) int {}
// The function signature is as follows
var maxArea = function(height) {}
This problem is very similar to the "Trapping Rain Water" problem, and you can completely apply the same approach from the previous article, making it even simpler. The main difference between the two problems is:
The "Trapping Rain Water" problem presents a histogram-like structure where each horizontal coordinate has a width, whereas in this problem, each horizontal coordinate is a vertical line without any width.
In our previous discussion, we spent a lot of time on l_max
and r_max
to calculate how much water height[i]
could hold. In this problem, since height[i]
has no width, it becomes much easier to handle.
For example, in the "Trapping Rain Water" problem, if you know the heights of height[left]
and height[right]
, can you calculate how much water can be trapped between left
and right
?
No, because you don't know the exact amount of water each pillar between left
and right
can hold. You need to calculate it using l_max
and r_max
for each pillar.
Conversely, for this problem, if you know the heights of height[left]
and height[right]
, can you calculate how much water can be trapped between left
and right
?
Yes, because in this problem, the vertical lines have no width, so the amount of water that can be trapped between left
and right
is:
min(height[left], height[right]) * (right - left)
Similar to the "Trapping Rain Water" problem, the height is determined by the smaller value between height[left]
and height[right]
.
The approach to solving this problem is still the two-pointer technique:
Use two pointers, left
and right
, to move towards the center from both ends. As you move, calculate the area of the rectangle between [left, right]
, and the maximum area value is the answer.
Let's directly look at the solution code:
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int res = 0;
while (left < right) {
// the area of the rectangle between [left, right]
int cur_area = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, cur_area);
// two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
}
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int res = 0;
while (left < right) {
// the area of the rectangle between [left, right]
int cur_area = min(height[left], height[right]) * (right - left);
res = max(res, cur_area);
// two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
};
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
res = 0
while left < right:
# the area of the rectangle between [left, right]
cur_area = min(height[left], height[right]) * (right - left)
res = max(res, cur_area)
# two-pointer technique, move the lower side
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
func maxArea(height []int) int {
left, right := 0, len(height)-1
res := 0
for left < right {
// the area of the rectangle between [left, right]
curArea := min(height[left], height[right]) * (right - left)
res = max(res, curArea)
// two-pointer technique, move the lower side
if height[left] < height[right] {
left++
} else {
right--
}
}
return res
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
var maxArea = function(height) {
let left = 0, right = height.length - 1;
let res = 0;
while (left < right) {
// the area of the rectangle between [left, right]
let cur_area = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, cur_area);
// two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
};
The code is similar to the problem of trapping rainwater. However, some readers might wonder why the following if
statement moves the lower side:
// Two-pointer technique, move the lower side
if (height[left] < height[right]) {
left++;
} else {
right--;
}
It's actually easy to understand because the height of the rectangle is determined by min(height[left], height[right])
, which is the shorter side:
If you move the shorter side, that side might become taller, increasing the height of the rectangle, and thus there is a "possibility" that the area of the rectangle will increase. Conversely, if you move the taller side, the height of the rectangle will not increase regardless, so it is impossible to make the area of the rectangle larger.
With this, the problem is also solved.