42. Trapping Rain Water

Prompt

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

Examples

• 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

Solutions

Array Solution

In C++

int trap(vector<int>& height) {
	size_t n = height.size();
 
	vector<int> max_scan_l(n);
	inclusive_scan(
		height.begin(), height.end(), 
		max_scan_l.begin(),
		ranges::max
	);
 
	vector<int> max_scan_r(n);
	inclusive_scan(
		height.rbegin(), height.rend(), 
		max_scan_r.rbegin(),
		ranges::max
	);
 
	std::vector<int> min_scan(n);
	transform(
		max_scan_l.begin(), max_scan_l.end(),
		max_scan_r.begin(),
		min_scan.begin(),
		ranges::min
	);
 
	std::vector<int> areas(n);
	transform(
		min_scan.begin(), min_scan.end(),
		height.begin(),
		areas.begin(),
		minus<void>()
	);
 
	int total_area = accumulate(areas.begin(), areas.end(), 0);
	return total_area;
}

Explanation

The code is pretty self explanatory, but to summarize we do:

sum(min(max_scan_l(id), max_scan_r(id)) - id)`

Unfortunately, the code is not that concise in C++, but whatever. The idea behind this logic is that we need to be able to construct an array of area of water per index. This requires information about the left and right bounding walls which we get from the scans.

While probably easiest to read, and immediately understand, this code uses too much space.

Here is an example output to show the idea:

0 1 0 2 1 0 1 3 2 1 2 1  <- A, Input Array
0 1 1 2 2 2 2 3 3 3 3 3  <- B, Prefix Max Scan
3 3 3 3 3 3 3 3 2 2 2 1  <- C, Suffix Max Scan
0 1 1 2 2 2 2 3 2 2 2 1  <- D, Min(B, C)
0 0 1 0 1 2 1 0 0 1 0 0  <- E, D - A
6 <- sum E

Big O Analysis

Time Complexity

$O(n)$

Auxiliary Space Complexity

$O(n)$

Space Efficient Array Solution

In C++

int trap(const std::vector<int>& height) {
	const size_t n = height.size();
	if (n < 3) return 0;
 
	vector<int> max_scan_r(n);
	inclusive_scan(
		height.rbegin(), height.rend(), 
		max_scan_r.rbegin(), 
		ranges::max
	);
 
	int l_max = height[0];
	int total_area = 0;
	for (size_t i = 0; i < n; ++i) {
		l_max = max(l_max, height[i]);
		total_area += min(l_max, max_scan_r[i]) - height[i];
	}
	return total_area;
}

Explanation

The idea here is to use the same intuition from the above Array Solution, but only store the suffix max scan, because everything else can be calculate on the fly during a normal left to right iteration through the input array. This solution obviously has way better space, and actually runs in “0 ms” as a result. However, it is possible to have constant space, so we can do better.

Big O Analysis

Time Complexity

$O(n)$

Auxiliary Space Complexity

$O(n)$

Optimal Two Pointers Solution

In C++

int trap(const std::vector<int>& height) {
	const size_t n = height.size();
	if (n < 3) return 0;
 
	int total_area = 0;
	size_t li = 0; 
	size_t ri = n - 1;
	int lmax = height[li];
	int rmax = height[ri];
	while (li < ri) {
		while (lmax <= rmax && li < ri) {
			total_area += lmax - height[li];
			li++;
			lmax = max(lmax, height[li]);
		}
		while (lmax >= rmax && li < ri) {
			total_area += rmax - height[ri];
			ri--;
			rmax = max(rmax, height[ri]);
		}
	}
	return total_area;
}

Explanation

This solution is kind of similar to QuickSort’s Hoare Partitioning, as the two pointers work in a similar way. The idea is basically that the left and right max must either be less than or equal, or greater than or equal to one another. Let’s say the left max is less than or equal to the right max. From the perspective of the left max, it doesn’t matter if there is some higher max than the current right max further within the array. All that matters is that there exists a wall on the other side to hold all water at and below the height of the current left max. The reciprocal is true from the perspective of the right max, due to symmetry, i.e. if we look at the problem in a mirror, the perspectives swap. Therefore they are equivalent. Based on this, we use Two Pointers, to go through the array, adding everything below the current waterline for the current index to thte total area.

Big O Analysis

Time Complexity

$O(n)$

Auxiliary Space Complexity

$O(1)$

Optimal Two Pointers Solution 2

In C++

int trap(const std::vector<int>& height) {
	const size_t n = height.size();
	if (n < 3) return 0;
 
	int total_area = 0;
	size_t li = 0; 
	size_t ri = n - 1;
	int lmax = height[li];
	int rmax = height[ri];
	while (li < ri) {
		if (lmax <= rmax) {
			total_area += lmax - height[li];
			li++;
			lmax = max(lmax, height[li]);
		}
		else {
			total_area += rmax - height[ri];
			ri--;
			rmax = max(rmax, height[ri]);
		}
	}
	return total_area;
}

Explanation

This is the same as the previous Optimal Two Pointers Solution, except for the logic is less complicated.

Big O Analysis

Time Complexity

$O(n)$

Auxiliary Space Complexity

$O(1)$