add a solution for 11

fishercoder1534 · fishercoder1534 · commit e3c7c87545ee · 2021-10-22T10:33:55.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_11.java b/src/main/java/com/fishercoder/solutions/_11.java
@@ -2,18 +2,38 @@
 
 public class _11 {
     public static class Solution1 {
+        /**
+         * Time: O(n^2)
+         * This brute force solution is NOT accepted on LeetCode due to TLE.
+         */
+        public int maxArea(int[] height) {
+            int maxArea = 0;
+            for (int left = 0; left < height.length - 1; left++) {
+                for (int right = height.length - 1; left < right; right--) {
+                    int area = (right - left) * Math.min(height[left], height[right]);
+                    maxArea = Math.max(maxArea, area);
+                }
+            }
+            return maxArea;
+        }
+    }
+
+    public static class Solution2 {
+        /**
+         * Two pointer technique.
+         * Well explained here: https://leetcode.com/problems/container-with-most-water/discuss/6100/Simple-and-clear-proofexplanation
+         */
         public int maxArea(int[] height) {
             int max = 0;
-            int i = 0;
-            int j = height.length - 1;
-            while (i < j) {
-                max = Math.max(Math.min(height[i], height[j]) * (j - i), max);
-                if (height[i] <= height[j]) {
-                    // we need to find the shorter one,
-                    // then calculate its area
-                    i++;
+            int left = 0;
+            int right = height.length - 1;
+            while (left < right) {
+                max = Math.max(Math.min(height[left], height[right]) * (right - left), max);
+                if (height[left] <= height[right]) {
+                    /**if this height is shorter, then we'll need to move it to the right to find a higher one so that it's possible to find a larger area.*/
+                    left++;
                 } else {
-                    j--;
+                    right--;
                 }
             }
             return max;
diff --git a/src/test/java/com/fishercoder/_11Test.java b/src/test/java/com/fishercoder/_11Test.java
@@ -8,17 +8,22 @@
 
 public class _11Test {
     private static _11.Solution1 solution1;
+    private static _11.Solution2 solution2;
     private static int[] height;
+    private static int expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _11.Solution1();
+        solution2 = new _11.Solution2();
     }
 
     @Test
     public void test1() {
         height = new int[]{1, 1};
-        assertEquals(1, solution1.maxArea(height));
+        expected = 1;
+        assertEquals(expected, solution1.maxArea(height));
+        assertEquals(expected, solution2.maxArea(height));
     }
 
 }
