Trapping Rain Water (Java + Python)

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: DP 

 To calculate the total volume is to calculate volumes can hold at each position.

 To calculate how many volumes can hold at each position is to calculate it's right bound height  and right bound height 

Current position can hold water only at the situation when the low side among both sides higher than the height at current position

If so,  use the lower one minus current height as height to multiply the width 1 is how many volumes can hold at current position

How to calculate the height of both sides for each position? We can apply DP theory to record  highest height bound can get from left to current and highest height bound can get from right to current  

HigehstLeftSideHeight so far from giving example, should be  0,1,1,2,2,2,2,3,3,3,3,3

HighestRightSideHeight so far for given example is 1,2,2,2,3,3,3,3,3,3,3,3

Then loop through giving array for each position to calculate how many volumes can hold there and update the total volume it can hold

	/*
	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.
	// To calculate the total volume is to calculate volume can hold at
	// each position.
	// To calculate how many volume can hold at each position is to calculate it's right bound height
	// and right bound height
	//Current position can hold water only at situation when the lowest side among both sides higher than the height at current position
	//if so, use the lower one minues current height as height to multily the width 1 is how many volume can hold at current position
	// How to calculate the height of both sides for each position? we can apply DP theory
	// to record hightest height bound can get from left to current and highest height bound can get from right to current
	// HigehstLeftSideHeight so far for given example should be
	// 0,1,1,2,2,2,2,3,3,3,3,3
	// HighestRightSideHeight so far for given example is
	// 1,2,2,2,3,3,3,3,3,3,3,3
	// then loop through given array for each posiiton calculate how many volume can hold there and update the total voluem it can hold
	*/
	public class Solution {
	public int trap(int[] A) {
	if (A==null ||A.length==0){
	return 0;
	}
	int[] highestLeftSoFar=new int[A.length];
	int[] highestRightSoFar=new int[A.length];
	// left->right
	for (int i=0; i<highestLeftSoFar.length; i++){
	highestLeftSoFar[i]=i==0?A[i]:Math.max(A[i], highestLeftSoFar[i-1]);
	}
	// right -> left
	for (int i=A.length-1; i>=0; i--){
	highestRightSoFar[i]=i==A.length-1?A[i]:Math.max(A[i], highestRightSoFar[i+1]);
	}
	int totalVolume=0;
	for (int i=0; i<A.length; i++){
	int height=Math.min(highestLeftSoFar[i], highestRightSoFar[i]);
	if (height>A[i]){
	height=height-A[i];
	totalVolume+=height*1;
	}
	}
	return totalVolume;
	}
	}

view raw TrappingRainWater.java hosted with ❤ by GitHub

	"""
	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!
	"""
	class Solution:
	# @param A, a list of integers
	# @return an integer
	def trap(self, A):
	if not A:
	return 0
	highestLeftSoFar=[]
	highestRightSoFar=[]
	for i in range(len(A)):
	highestLeftSoFar.append(A[i] if i==0 else max(A[i], highestLeftSoFar[-1]))
	for i in range(len(A)-1, -1, -1):
	highestRightSoFar.insert(0,A[i] if i==len(A)-1 else max(A[i], highestRightSoFar[0]))
	totalVolume=0;
	for i, currentHeight in enumerate(A):
	minSideHeight=min(highestLeftSoFar[i], highestRightSoFar[i])
	if minSideHeight>currentHeight:
	totalVolume+=(minSideHeight-currentHeight)*1
	return totalVolume

view raw TrappingRainWater.py hosted with ❤ by GitHub