phyous · August 29, 2015 14:00 · Apr 23, 2014 · Apr 23, 2014 · Apr 23, 2014
diff --git a/CalculateWater → CalculateWater.java b/CalculateWater → CalculateWater.java
diff --git a/CalculateWater b/CalculateWater
@@ -1,8 +1,10 @@
 /**
  * Trapping Water
  *
- * A one-dimensional container is specified by an array of n nonnegative integers, specifying the eight of each
- * unit-width rectangle. Design an algorithm for computing the capacity of the container.
+ * A one-dimensional container is specified by an array of
+ * n nonnegative integers, specifying the eight of each
+ * unit-width rectangle. Design an algorithm for computing
+ * the capacity of the container.
  *
  * Ex: (X = Occupied, ▤ = Water)
  *
@@ -16,17 +18,29 @@
 public class TrappingWater {
 
     /**
-     * The key to this problem is realizing that the water poured into the "container" will flow out of bounds on the
-     * left and right sides (index < 0 & index > array.length). If we are able to find the highest point in the array
-     * (maxVal), we can divide the array into two segments (left and right) around this midpoint. For both left & right,
-     * there will be a region of increasing altitude, and decreasing altitude. In the regions of decreasing altitude,
-     * this is where water will be stored. All we need to do is find the local maxima in each left and right region.
+     * The key to this problem is realizing that the water
+     * poured into the "container" will flow out of bounds
+     * on the left and right sides (index < 0 &
+     * index > array.length). If we are able to find the
+     * highest point in the array (maxVal), we can divide
+     * the array into two segments (left and right) around
+     * this midpoint. For both left & right, there will be
+     * a region of increasing altitude, and decreasing
+     * altitude. In the regions of decreasing altitude,
+     * this is where water will be stored. All we need to
+     * do is find the local maxima in each left and right
+     * region.
      *
      * Thus, the problem can be solved in 3 phases:
-     * 1)   Find the column index with the highest height (maxIndex)
-     * 2)   Calculate water in the left hand side: For i = [0, maxIndex-1] if we find a new local maxima, store it,
-     *      otherwise we have water trapped and we can caluculate the volume
-     * 3)   Calculate water in the right hand side in a similar manner for i = [maxIndex+1, array.length-1]
+     * 1)   Find the column index with the highest height
+     *      (maxIndex)
+     * 2)   Calculate water in the left hand side: For
+     *      i = [0, maxIndex-1] if we find a new local
+     *      maxima, store it, otherwise we have water
+     *      trapped and we can caluculate the volume
+     * 3)   Calculate water in the right hand side in a
+     *      similar manner for i = [maxIndex+1,
+     *      array.length-1]
      *
      * Solution is O(N) time, O(1) space
      */
@@ -79,19 +93,25 @@ public class TrappingWater {
         testCalculateWater(3, testData3, 0);
         int[] testData4 = {1, 0, 1, 0, 1, 0, 1, 0};
         testCalculateWater(4, testData4, 3);
-        int[] testData5 = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
+        int[] testData5 = {Integer.MAX_VALUE, 
+                Integer.MAX_VALUE, 
+                Integer.MAX_VALUE, 
+                Integer.MAX_VALUE};
         testCalculateWater(5, testData5, 0);
     }
 
-    private static void testCalculateWater(int testId, int[] input, int expectedVal) {
+    private static void testCalculateWater(int testId, 
+                                           int[] input, 
+                                           int expectedVal) {
         int ret = calculateWater(input);
         if (ret == expectedVal) {
             System.out.println("PASS");
         } else {
             System.out.println(
-                    String.format("Test %d: FAIL\n\tExpected return = %d\n\tActual return = %d",
+                    String.format(
+            "Test %d: FAIL\n\tExpected return = %d\n\tActual return = %d",
                             testId, expectedVal, ret)
             );
         }
     }
-}
+}
diff --git a/CalculateWater b/CalculateWater
@@ -0,0 +1,97 @@
+/**
+ * Trapping Water
+ *
+ * A one-dimensional container is specified by an array of n nonnegative integers, specifying the eight of each
+ * unit-width rectangle. Design an algorithm for computing the capacity of the container.
+ *
+ * Ex: (X = Occupied, ▤ = Water)
+ *
+ *       X               X
+ *     XXX             XXX
+ *    XXXX   X        XXXX▤▤▤X
+ *  X XXXX X X ==>  X▤XXXX▤X▤X ==> 1+2+1+3 = 7
+ * XXXXXXXXX X     XXXXXXXXX▤X
+ * 12134451203
+ */
+public class TrappingWater {
+
+    /**
+     * The key to this problem is realizing that the water poured into the "container" will flow out of bounds on the
+     * left and right sides (index < 0 & index > array.length). If we are able to find the highest point in the array
+     * (maxVal), we can divide the array into two segments (left and right) around this midpoint. For both left & right,
+     * there will be a region of increasing altitude, and decreasing altitude. In the regions of decreasing altitude,
+     * this is where water will be stored. All we need to do is find the local maxima in each left and right region.
+     *
+     * Thus, the problem can be solved in 3 phases:
+     * 1)   Find the column index with the highest height (maxIndex)
+     * 2)   Calculate water in the left hand side: For i = [0, maxIndex-1] if we find a new local maxima, store it,
+     *      otherwise we have water trapped and we can caluculate the volume
+     * 3)   Calculate water in the right hand side in a similar manner for i = [maxIndex+1, array.length-1]
+     *
+     * Solution is O(N) time, O(1) space
+     */
+    private static int calculateWater(int[] heights) {
+        // Arrays less than 3 can't contain water
+        if (heights.length < 3 || heights == null) {
+            return 0;
+        }
+
+        // 1) Calculate max height index
+        int maxVal = 0, maxIndex = 0;
+        for (int i = 0; i < heights.length; i++) {
+            if (heights[i] > maxVal) {
+                maxVal = heights[i];
+                maxIndex = i;
+            }
+        }
+
+        // 2) Calculate water in left portion of array
+        int count = 0;
+        int leftMax = 0;
+        for (int i = 0; i < maxIndex - 1; i++) {
+            if (heights[i] > leftMax) {
+                leftMax = heights[i];
+            } else {
+                count += leftMax = heights[i];
+            }
+        }
+
+        // 3) Calculate water in right portion of array
+        int rightMax = 0;
+        for (int i = heights.length - 1; i > maxIndex; i--) {
+            if (heights[i] > rightMax) {
+                rightMax = heights[i];
+            } else {
+                count += rightMax - heights[i];
+            }
+        }
+
+        return count;
+    }
+
+    // --- Test code
+    public static void main(String[] args) {
+        int[] testData1 = {1};
+        testCalculateWater(1, testData1, 0);
+        int[] testData2 = {1, 2, 1, 3, 4, 4, 5, 1, 2, 0, 3};
+        testCalculateWater(2, testData2, 7);
+        int[] testData3 = {1, 2, 3, 4, 3, 2, 1};
+        testCalculateWater(3, testData3, 0);
+        int[] testData4 = {1, 0, 1, 0, 1, 0, 1, 0};
+        testCalculateWater(4, testData4, 3);
+        int[] testData5 = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
+        testCalculateWater(5, testData5, 0);
+    }
+
+    private static void testCalculateWater(int testId, int[] input, int expectedVal) {
+        int ret = calculateWater(input);
+        if (ret == expectedVal) {
+            System.out.println("PASS");
+        } else {
+            System.out.println(
+                    String.format("Test %d: FAIL\n\tExpected return = %d\n\tActual return = %d",
+                            testId, expectedVal, ret)
+            );
+        }
+    }
+}