leetcode Problem 01 first try

shekhargulati · shekhargulati · commit 3a0fbe324602 · 2016-03-02T17:26:24.000+05:30
diff --git a/java8/src/main/java/com/shekhargulati/leetcode/Problem01.java b/java8/src/main/java/com/shekhargulati/leetcode/Problem01.java
@@ -12,25 +12,42 @@
  */
 public class Problem01 {
 
+    /*
+    This solution is O(n)
+     */
     public static int[] twoSum(int[] numbers, int target) {
         /*
             Algorithm:
-            1. Create a new array with filtering all the numbers less than the target.
-            2. Iterate over the filtered array to find a pair which sum equal to target
+            1. Store all the number and their indexes in a Map
+            2. Create a new array with filtering all the numbers less than the target.
+            3. Iterate over the filtered array.
+            4. For each number find the second number by subtracting it from the target
+            5. If Map contains the second number then we have found the pair
+            6. Short circuit the loop and return the result.
          */
+        Map<Integer, Integer> numberAndIndex = new HashMap<>();
+        for (int i = 0; i < numbers.length; i++) {
+            numberAndIndex.put(numbers[i], i);
+        }
+
         int[] numbersLessThanTarget = Arrays.stream(numbers).filter(i -> i < target).toArray();
 
         for (int i = 0; i < numbersLessThanTarget.length - 1; i++) {
-            for (int j = i + 1; j < numbersLessThanTarget.length; j++) {
-                if ((numbersLessThanTarget[i] + numbersLessThanTarget[j]) == target) {
-                    return new int[]{numbersLessThanTarget[i], numbersLessThanTarget[j]};
-                }
+            int first = numbersLessThanTarget[i];
+            int second = target - first;
+            if (numberAndIndex.containsKey(second)) {
+                return new int[]{i, numberAndIndex.get(second)};
             }
+
         }
         return new int[0];
     }
 
-    public static int[] twoSumIndexes(int[] numbers, int target) {
+
+    /*
+    This solution in O(n^2)
+     */
+    public static int[] twoSum_2(int[] numbers, int target) {
         /*
             Algorithm:
             1. Create a new array with filtering all the numbers less than the target.
@@ -53,4 +70,6 @@ public static int[] twoSumIndexes(int[] numbers, int target) {
         }
         return new int[0];
     }
+
+
 }
diff --git a/java8/src/test/java/com/shekhargulati/leetcode/Problem01Test.java b/java8/src/test/java/com/shekhargulati/leetcode/Problem01Test.java
@@ -14,28 +14,16 @@ public class Problem01Test {
     @Test
     public void shouldFindTwoNumberWhoseSumIsEqualToTarget() throws Exception {
         int[] pairs = Problem01.twoSum(new int[]{2, 7, 11, 15}, 9);
-        assertTrue(Arrays.equals(pairs, new int[]{2, 7}));
+        assertTrue(Arrays.equals(pairs, new int[]{0, 1}));
     }
 
     @Test
     public void shouldFindTwoNumberWhoseSumIsEqualToTarget2() throws Exception {
         int[] pairs = Problem01.twoSum(new int[]{10, 17, 11, 30}, 21);
-        assertTrue(Arrays.equals(pairs, new int[]{10, 11}));
-    }
-
-
-    @Test
-    public void shouldFindTwoNumberWhoseSumIsEqualToTarget_index() throws Exception {
-        int[] pairs = Problem01.twoSumIndexes(new int[]{2, 7, 11, 15}, 9);
-        assertTrue(Arrays.equals(pairs, new int[]{0, 1}));
-    }
-
-    @Test
-    public void shouldFindTwoNumberWhoseSumIsEqualToTarget2_index() throws Exception {
-        int[] pairs = Problem01.twoSumIndexes(new int[]{10, 17, 11, 30}, 21);
         assertTrue(Arrays.equals(pairs, new int[]{0, 2}));
     }
 
+
     @Test
     public void shouldWorkOnARandomArray() throws Exception {
         int[] numbers = new Random().ints(100000, 1, 100000).toArray();
