LeetCode Q42: Trapping Rain Water (hard)

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.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

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!

Solution 1:

The solution is very straight forward once you understand what the question really ask about. We basically need to find the highest and 2nd highest bar between which water can be trapped. To find all pairs of highest and 2nd highest, we use recursion.

	class Solution {
	public:
	int ComputeWater(vector<int>& height, int l, int r){
	int minv=min(height[l], height[r]);
	int water=0;
	for(int i=l+1; i<r; i++){
	water+=minv-height[i];
	}
	return water;
	}
	int Divide(vector<int>& height, int l, int r){
	int maxheight=0;
	int maxheightIdx=l+1;
	for(int i=l+1; i<r; ++i){
	if(height[i]>maxheight){
	maxheight=height[i];
	maxheightIdx=i;
	}
	}
	if(maxheight<=min(height[l], height[r]))
	return ComputeWater(height, l, r);
	int water0=Divide(height, l, maxheightIdx);
	int water1=Divide(height, maxheightIdx, r);
	return water0+water1;
	}
	int trap(vector<int>& height) {
	if(height.empty())
	return 0;
	return Divide(height, 0, height.size()-1);
	}
	};

view raw Q42TrappingRainWater.cpp hosted with ❤ by GitHub

Solution 2:
My another code. One observation is given highest bar of the problem, it separates array to two parts. In left parts, heights of all bars that can hold water are in ascending order, and in right part, heights of all bars that can hold water are in descending order. So, we can finish problem in two passes

	class Solution {
	public:
	void helper(vector<int>& height, int maxIdx, int& res){
	int p0=0, p1=0;
	for(int p1=0; p1<=maxIdx; p1++){
	if(height[p1]>=height[p0]){
	for(int j=p0+1; j<p1; j++)
	res = res + height[p0]-height[j];
	p0=p1;
	}
	}
	}
	int trap(vector<int>& height) {
	if(height.empty())
	return 0;
	int maxv=INT_MIN;
	int maxIdx=0;
	for(int i=0; i<height.size(); i++){
	if(height[i]>=maxv){
	maxv=height[i];
	maxIdx=i;
	}
	}
	int res=0;
	helper(height, maxIdx, res);
	reverse(height.begin(), height.end());
	helper(height, height.size()-1-maxIdx, res);
	return res;
	}
	};

view raw Q42-2.cpp hosted with ❤ by GitHub

Solution 3:
Similar to solution2, but can be done in one pass. Using two pointers. Two pointers will meet at the highest bar.

	public class Solution {
	public int trap(int[] heights) {
	if ( heights.length <= 2 ) { return 0; }
	int left = 0, right = heights.length-1, totalArea = 0;
	int leftMaxHeight = heights[left], rightMaxHeight = heights[right];
	while ( left < right ) {
	if ( heights[left] < heights[right] ) {
	leftMaxHeight = Math.max(leftMaxHeight, heights[++left]);
	totalArea += leftMaxHeight-heights[left];
	} else {
	rightMaxHeight = Math.max(rightMaxHeight, heights[--right]);
	totalArea += rightMaxHeight-heights[right];
	}
	}
	return totalArea;
	}
	}

view raw Q42-3.cpp hosted with ❤ by GitHub