package general;

/**
 * You have a two-dimensional view of a terrain of uneven land with sharp ups
 * and downs (always perpendicular changes in terrain structure). The terrain
 * can be represented using 'N' non-negative integers given to you as an array
 * of integers, with each integer representing the height of the terrain at that
 * point in the sequence. Lets assume that each piece of the terrain rises from
 * a common base situated at the same height (ground 0). For example, the array:
 * {5,1,3,2,6} can be imagined as a bar graph diagram on an X-Y plane with
 * X-axis representing the base of the terrain and Y-axis representing the
 * height of each piece of the terrain.
 *
 * Now there is a sudden downpour of rain over this uneven terrain, and water
 * gets accumulated in the pits formed due to the ups and downs. Given the
 * terrain, your task is to write a function that can find the accumulated rain
 * water.
 *
 * Here is a picture showing the above case: http://i.imgur.com/3pFFU.png
 *
 * Examples:
 *
 * [1]
 *
 * Array: {5,1}. Answer: 0 units of water. Reason: There are no pits :-(
 *
 * [2]
 *
 * Array: {0,2,1,2}. Answer: 1 unit of water. Reason: 1 unit of water
 * accumulated between 2nd and 4th pieces of the terrain
 *
 * @author Kowshik Prakasam (kowshik@gmail.com)
 */
public class RainWater {

	/**
	 * Calculates rain water accumulated on the terrain between various peaks in
	 * the terrain.
	 *
	 * @param terrain
	 *            terrain described by an array of positive integers, each
	 *            representing the height at a particular point.
	 * @return amount of water accumulated on the given terrain.
	 */
	public static long findAccumulatedWater(int[] terrain) {
		if (terrain == null) {
			return 0;
		}
		int maxIndex = 0;
		long totalWater = 0;
		long tempWater = 0;

		for (int index = maxIndex + 1; index < terrain.length; index++) {
			if (terrain[index] >= terrain[maxIndex]) {
				totalWater += tempWater;
				tempWater = 0; // flushing temp water stored
				maxIndex = index;
			} else {
				tempWater += terrain[maxIndex] - terrain[index];
			}
		}

		tempWater = 0;
		int reverseMaxIndex = terrain.length - 1;
		for (int index = reverseMaxIndex - 1; index >= maxIndex; index--) {
			if (terrain[index] >= terrain[reverseMaxIndex]) {
				totalWater += tempWater;
				tempWater = 0; // flushing temp water stored
				reverseMaxIndex = index;
			} else {
				tempWater += terrain[reverseMaxIndex] - terrain[index];
			}
		}

		return totalWater;
	}
}

@@ -684,17 +684,18 @@
 rain.%0A *
+ 
 %0A
-
  * Now t
@@ -931,16 +931,17 @@
 ater.%0A *
+ 
 %0A * Here
@@ -1009,16 +1009,17 @@
 U.png%0A *
+ 
 %0A * Exam
@@ -1026,16 +1026,17 @@
 ples:%0A *
+ 
 %0A * %5B1%5D%0A
@@ -1033,24 +1033,25 @@
 * %0A * %5B1%5D%0A *
+ 
 %0A * Array: %7B
@@ -1114,16 +1114,17 @@
 s :-(%0A *
+ 
 %0A * %5B2%5D%0A
@@ -1125,16 +1125,17 @@
 * %5B2%5D%0A *
+ 
 %0A * Arra
@@ -1258,59 +1258,8 @@
 ain%0A
- *%0A * @author Kowshik Prakasam (kowshik@gmail.com)%0A
  */%0A
@@ -1384,19 +1384,20 @@
 errain.%0A
-
 %09 *
+ 
 %0A%09 * @pa

Remove @author