42. Trapping Rain Water #

Problem #

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map 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. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Problem Summary #

Starting from the x-axis, given an array, the numbers in the array represent, starting from point (0,0), bars with a width of 1 unit and a height equal to the value of the array element. If it rains, how many units of water can such a container hold?

Solution Ideas #

• The value of each element in the array can be imagined as a cylindrical tube with walls on both the left and right. For example, for the second element 1 on the left in the figure below, the current maximum element on the left is 2, so water of height 2 will be stored above 1 (because it is imagined as having tube walls on both sides). The idea of this problem is to start the left pointer from 0 and scan to the right, and start the right pointer from the far right and scan to the left. Additionally, 2 variables are needed to record the maximum height on the left and the maximum height on the right respectively. During the process of scanning the array elements, if the height of the left pointer is smaller than the height of the right pointer, keep moving the left pointer; otherwise, move the right pointer. The loop termination condition is that it ends after the left and right pointers meet. As long as the height of an element in the array is smaller than the saved local maximum height, accumulate the value of res; otherwise, update the local maximum height. The final answer is the value of res.
• To abstract it, this problem aims to find, for each i, the maximum value on its left, leftMax, and the maximum value on its right, rightMax, then min(leftMax, rightMax) is the height of water that can be trapped. The left and right pointers are cursor pointers moving from both sides toward the middle. The most naive solution is, for each index i, to loop left to find the first maximum value, loop right to find the first maximum value, then take the smaller of these two maximum values, which is the current rainwater height. This approach has high time complexity and wastes many loops. As i moves from left to right, the maximum value can be maintained dynamically. The maximum value on the right is maintained by the cursor pointer on the right. Scanning the indices once from left to right and traversing the indices once from both sides toward the middle produce the same result; every index is traversed once.
  
• The width of each i is fixed at 1, so for each “pit”, only its height needs to be calculated, that is, the amount of rainwater this current “pit” can accumulate. Finally, adding up the rainwater in each “pit” in sequence gives the total amount of rainwater that can be trapped.
  

Code #

package leetcode

func trap(height []int) int {
	res, left, right, maxLeft, maxRight := 0, 0, len(height)-1, 0, 0
	for left <= right {
		if height[left] <= height[right] {
			if height[left] > maxLeft {
				maxLeft = height[left]
			} else {
				res += maxLeft - height[left]
			}
			left++
		} else {
			if height[right] >= maxRight {
				maxRight = height[right]
			} else {
				res += maxRight - height[right]
			}
			right--
		}
	}
	return res
}