LintCode 363 · Trapping Rain Water.java

	public class Solution {
	/**
	* @param heights: a list of integers
	* @return: a integer
	*/
	public int trapRainWater(int[] heights) {
	// handle corner cases
	if (heights == null || heights.length == 0) {
	return 0;
	}
	int n = heights.length;
	// 1st pass - prefixMax - O(n)
	int[] prefixMax = new int[n];
	prefixMax[0] = 0;
	for (int i = 1; i < n; i++) {
	prefixMax[i] = Math.max(heights[i - 1], prefixMax[i - 1]);
	}
	// 2nd pass - postfixMax - O(n)
	int[] postfixMax = new int[n];
	postfixMax[n - 1] = 0;
	for (int i = n - 2; i >= 0; i--) {
	postfixMax[i] = Math.max(heights[i + 1], postfixMax[i + 1]);
	}
	// 3rd pass - get each water and sum - O(n)
	int sum = 0;
	for (int i = 1; i < n - 1; i++) {
	int currentHeight = heights[i];
	int boundaryMin = Math.min(prefixMax[i], postfixMax[i]);
	sum += (boundaryMin > currentHeight) ? boundaryMin - currentHeight : 0;
	}
	return sum;
	}
	}

view raw LintCode 363 · Trapping Rain Water.java hosted with ❤ by GitHub