Trapping Rain Water @LeetCode

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!

	package leetcode;
	/**
	* Solution: for i, the water it trapped is decided by leftMostHeight and rightMostHeight.
	* if Math.min(left, right) > A[i]. for i, water is Math.min(left, right) - A[i]
	* Two pass. calculate maxLeft first, and maxRight, at the same time, calculate sum.
	*
	* max = A[0] and max = A[A.length - 1] doesn't matter because i= 0 or A.length - 1 will not trap water.
	*
	* Reference:
	* http://fisherlei.blogspot.com/2013/01/leetcode-trapping-rain-water.html
	* http://blog.unieagle.net/2012/10/31/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Atrapping-rain-water/
	*
	* @author jeffwan
	* @date Apr 3, 2014
	*/
	public class TrappingRainWater {
	public int trap(int[] A) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int sum = 0;
	int max = A[0];
	int[] maxLeft = new int[A.length];
	int[] maxRight = new int[A.length];
	maxLeft[0] = 0;
	// Get max left for every i.
	for (int i = 1; i < A.length - 1; i++) {
	maxLeft[i] = max;
	if (max < A[i]) {
	max = A[i];
	}
	}
	max = A[A.length - 1];
	maxRight[A.length - 1] = 0;
	// Get max left for every i.
	for (int i = A.length - 2; i > 0; i--) {
	maxRight[i] = max;
	if (max < A[i]) {
	max = A[i];
	}
	// Calculate trapped water
	if (Math.min(maxLeft[i], maxRight[i]) > A[i]) {
	sum += Math.min(maxLeft[i], maxRight[i]) - A[i];
	}
	}
	return sum;
	}
	}

view raw TrappingRainWater.java hosted with ❤ by GitHub