Problem

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.

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

Solution

Method 1 - Scan From Both Left and Right Side

This problem is similar to Candy distribution Problem. It can be solve by scanning from both sides and then get the total.

Observe that the trapped water on top of a single tower is depends on the space on top of it. A container space will be happened to be created on top of a tower if the tower is surrounded by larger towers in both left and right. In that sense, we need to find the leftmost and rightmost tower with height greater then current tower. Then rain accumulated on a tower is the difference between the height of minimum of these towers and the height of current tower. to sum up:

  • A ith bar can trap the water if and only if there exists a higher bar to the left and a higher bar to the right of ith bar.
  • To calculate how much amount of water the ith bar can trap, we need to look at the maximum height of the left bar and the maximum height of the right bar, then
    • The water level can be formed at ith bar is: waterLevel = min(maxLeft[i], maxRight[i])
    • If waterLevel >= height[i] then ith bar can trap waterLevel - height[i] amount of water.
  • To achieve in O(1) when looking at the maximum height of the bar on the left side and on the right side of ith bar, we pre-compute it:
    • Let maxLeft[i] is the maximum height of the bar on the left side of ith bar.
    • Let maxRight[i] is the maximum height of the bar on the right side of ith bar.
 trappedRain[i] = max{min{MaxLeft[i] , MaxRight[i]} - tower[i], 0}
 totalRain +=  trappedRain[i]55

Algo

  • Conduct a backwards sweep, noting MaxRight[i] as the furthest index of the tallest tower encountered.
  • Initialize MaxLeft[i] to 0.
  • Progress forwards, for each i:
    • Record MaxLeft[i] as the taller of the current tower or the preceding maximum.
    • Compute trapped rain atop tower i as trappedRain[i] = max(min(MaxLeft[i], MaxRight[i]) - tower[i], 0).
    • Increment totalRain by trappedRain[i].
  • Output totalRain.

Note that leftMax[0] = 0 and rightMax[n-1] = 0, as on left and right boundaries, we dont have anything.

Code

Java
public int trap(int[] height) {
	int n = height.length;
	int[] leftMax = new int[n], rightMax = new int[n];
	for (int i = 1; i<n; ++i) {
		leftMax[i] = Math.max(height[i - 1], leftMax[i - 1]);
	}
	for (int i = n - 2; i >= 0; --i) {
		rightMax[i] = Math.max(height[i + 1], rightMax[i + 1]);
	}

	int ans = 0;
	for (int i = 0; i<n; ++i) {
		int waterLevel = Math.min(leftMax[i], rightMax[i]);
		if (waterLevel >= height[i]) {
			ans += waterLevel - height[i];
		}
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Two Pointer Approach

We can use above approach without space using 2 pointers.

Code

Java
public int trap(int[] height) {
	int l = 0;
	int r = height.length - 1;
	int ans = 0;
	int leftmax = 0;
	int rightmax = 0;
	while (l <= r) {
		leftmax = Math.max(leftmax, height[l]);
		rightmax = Math.max(rightmax, height[r]);
		if (leftmax<rightmax) {
			// leftmax is smaller than rightmax, so the (leftmax-A[a]) water can be stored		
			ans += (leftmax - height[l]); 
			l++;
		} else {
			ans += (rightmax - height[r]);
			r--;
		}
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 3 - Monotonic Decreasing Stack

This problem is close to Largest Rectangle in Histogram Problem.

Just to add an equivalent solution with a cleaner structure.

  1. when the new height is lower than what is at the top of the stack, we push it.
  2. if the new height is higher than the top of the stack, we pop it, and deal with it. (the reason why I name it as deal is that, when we pop it from the stack, we will take care of whatever it needs to be computed. We will be done with it since then.
  3. To better understand how it works, intuitively, please manually imagine a case, [3, 2, 1, 0, 3]. And see the picture below.

See the three bubbles in the middle. They are the orders the deal was popped. Once it is popped, it takes care the area that it is responsible.

Code

Java
    public int trap(int[] height) {
	if (height == null || height.length < 2) {return 0;}
	
	Stack<Integer> stack = new Stack<>();
	int ans = 0, i = 0;
	while (i < height.length) {
		if (stack.isEmpty() || height[i] <= height[stack.peek()]) {
			stack.push(i++);
		} else {
			int prevIdx = stack.pop();
			if (!stack.isEmpty()) {
				// find the smaller height between the two sides
				int minHeight = Math.min(height[stack.peek()], height[i]);
				// calculate the area
				ans += (minHeight - height[prevIdx]) * (i - stack.peek() - 1);
			}
		}
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)