package LeetCode;

public class TrapingRainWater {

    public int trap1(int[] A) {
	if (A == null || A.length == 0) {
	    return 0;
	}

	int len = A.length;
	int left = 0;
	int right = len - 1;
	int leftHeight = 0;
	int rightHeight = 0;
	int water = 0;

	while (left < right) {
	    leftHeight = Math.max(leftHeight, A[left]);
	    rightHeight = Math.max(rightHeight, A[right]);
	    // Two ways to write the following if-condition
	    // This would also work: if (A[left] < A[right]) {
	    if (leftHeight < rightHeight) {
		// increase left pointer
		water += leftHeight - A[left];
		left++;
	    } else {
		water += rightHeight - A[right];
		right--;
	    }
	}
	return water;
    }

    // pass both
    // can solve the google interview problem as well
    public int trap(int[] A) {
	// Start typing your Java solution below
	// DO NOT write main() function

	int n = A.length;
	int i = 0, j = n - 1, sum = 0;

	while (i < j) {
	    // get the first one that is
	    // larger than the right one from the left
	    while (i < j && A[i] < A[i + 1]) {
		// google interview
		// sum+=A[i]
		i++;
	    }
	    // get the first one that is
	    // larger than the left on the right
	    while (i < j && A[j] < A[j - 1]) {
		j--;
	    }

	    if (i == j) {
		break;
	    }

	    if (A[i] > A[j]) {
		int k = j - 1;// which is smaller than A[j]
		while (A[k] < A[j] && k > i) {
		    sum += A[j] - A[k];
		    k--;
		}
		// now A[k] is greater than A[j]
		j = k;
	    } else {
		int k = i + 1;// which is smaller than A[i]
		// till we find the k that
		// A[k]>=A[i]
		while (A[k] < A[i] && k < j) {
		    sum += A[i] - A[k];
		    k++;
		}

		i = k;
	    }
	}

	return sum;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
	// TODO Auto-generated method stub
	TrapingRainWater t = new TrapingRainWater();
	System.out.println(t.trap(new int[] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2,
		1 }));
    }

}

@@ -45,24 +45,918 @@
 nWater %7B%0D%0A%0D%0A
+    /*%0D%0A     * The idea is: calculated the stored water at each index a and b in my%0D%0A     * code. At the start of every loop, update the current maximum height%0D%0A     * from left side (that is from A%5B0,1...a%5D) and the maximum height from%0D%0A     * right side(from A%5Bb,b+1...n-1%5D). if(leftmax%3Crightmax) then, at least%0D%0A     * (leftmax-A%5Ba%5D) water can definitely be stored no matter what happens%0D%0A     * between %5Ba,b%5D since we know there is a barrier at the%0D%0A     * rightside(rightmax%3Eleftmax). On the other side, we cannot store more%0D%0A     * water than (leftmax-A%5Ba%5D) at index a since the barrier at left is of%0D%0A     * height leftmax. So, we know the water that can be stored at index a is%0D%0A     * exactly (leftmax-A%5Ba%5D). The same logic applies to the case when%0D%0A     * (leftmax%3Erightmax). At each loop we can make a and b one step closer.%0D%0A     * Thus we can finish it in linear time.%0D%0A     */%0D%0A%0D%0A
     public i

add idea comments