How to Solve Drop Water Problem
The trapping rain water problem is very interesting and preforms frequently in interviews. So this paper will show how to solve the problem and explain how to optimize the solution step by step.
First of all, let's have a view on the problem:

In a word, an array represents an elevation map and hope you calculate how much rain water the elevation map can hold at most.
int trap(int[] height);
Now I will explain three approaches from shallow to deep: Brute force -> Using memorandum -> Using two pointers, and finally solve the problem with O(1) space complexity and O(N) time complexity.
When I saw this problem for the first time, I had no idea at all. I believe that many friends have the same experience. As for this kind of problem, we should not consider from the whole, but from the part; Just as the previous articles that talk about how to handle the string problem, don't consider how to handle the whole string. Instead, you should focus on how to handle each character among the string.
Therefore, we find that the thought of this problem is sample. Specifically, just for the position
i
as below, how much water can it hold?
Position
i
occupies 2 grids for holding water. Why it happens to hold 2 grids of water? Because the height of height[i]
is 0, and height[i]
can hold up to 2 grids of water, therefore there exists 2 - 0 = 2.But why the position
i
can hold 2 grids of water at most? Because the height of water column at position i
depends on both the hightest water column on the left and the highest water column on the right. We describe the height of the two highest water columns as l_max
and r_max
respectively. Thus the height at position i
is min(l_max, r_max)
.Further more, as for the position
i
, how much water it holds can be demonstrated as:water[i] = min(
# the highest column on the left
max(height[0..i]),
# the highest column on the right
max(height[i..end])
) - height[i]


This is the core idea of the problem, so we can program a simple brute approach:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
for (int i = 1; i < n - 1; i++) {
int l_max = 0, r_max = 0;
// find the highest column on the right
for (int j = i; j < n; j++)
r_max = max(r_max, height[j]);
// find the highest column on the right
for (int j = i; j >= 0; j--)
l_max = max(l_max, height[j]);
// if the position i itself is the highest column
// l_max == r_max == height[i]
ans += min(l_max, r_max) - height[i];
}
return ans;
}
According to the previous thought, the above approach seems very direct and brute. The time complexity is O(N^2) and the space complexity is O(1). However, it is obvious that the way of calculating
r_max
and l_max
is very clumsy, which the memorandum is generally introduced to optimize the way.In the previous brute approach, the
r_max
and l_max
are calculated at every position i
. So we can cache that calculation results, which avoids the stupid traversal at every time. Thus the time complexity will reasonably decline.Here two arrays
r_max
and l_max
are used to act the memo. l_max[i]
represents the highest column on the left of position i
and r_max[i]
represents the highest column on the right of position i
. These two arrays are calculated in advance to avoid duplicated calculation.int trap(vector<int>& height) {
if (height.empty()) return 0;
int n = height.size();
int ans = 0;
// arrays act the memo
vector<int> l_max(n), r_max(n);
// initialize 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 final result
for (int i = 1; i < n - 1; i++)
ans += min(l_max[i], r_max[i]) - height[i];
return ans;
}
Actually, the memo optimization has not much difference from the above brute approach, except that it avoids repeat calculation and reduces the time complexity to O(N). Although time complexity O(N) is already the best, but the space complexity is still O(N). So let's look at a more subtle approach that can reduce the space complexity to O(1).
The thought of this approach is exactly the same, but it is very ingenious in the way of implementation. We won't use the memo to cache calculation results in advance this time. Instead, we use two pointers to calculate during traversal and the space complexity will decline as a result.
First, look at some of the code:
int trap(vector<int>& height) {
int n = height.size();
int left = 0, right = n - 1;