number of boomerangs

fishercoder1534 · fishercoder1534 · commit a7ab08797ae3 · 2016-11-07T08:30:02.000-08:00
diff --git a/EASY/src/easy/NumberofBoomerangs.java b/EASY/src/easy/NumberofBoomerangs.java
@@ -0,0 +1,58 @@
+package easy;
+
+import java.util.HashMap;
+import java.util.Map;
+
+public class NumberofBoomerangs {
+    /**Looked at these two posts: https://discuss.leetcode.com/topic/66587/clean-java-solution-o-n-2-166ms and 
+     * https://discuss.leetcode.com/topic/66521/share-my-straightforward-solution-with-hashmap-o-n-2, basically,
+     * have a HashMap, key is the distance, value is the number of points that are this distance apart to this point.
+     * Note: we clear up this map every time after we traverse one point with the rest of the other points.
+     * 
+     * Time complexity: O(n^2)
+     * Space complexity: O(n)*/
+
+    public int numberOfBoomerangs(int[][] points) {
+        int result = 0;
+        if (points == null || points.length == 0 || points[0].length == 0)
+            return result;
+        int totalPts = points.length;
+        Map<Long, Integer> map = new HashMap();
+        for (int i = 0; i < totalPts; i++) {
+            for (int j = 0; j < totalPts; j++) {
+                if (i == j)
+                    continue;
+                long d = calcDistance(points[i], points[j]);
+                map.put(d, map.getOrDefault(d, 0) + 1);
+            }
+
+            for (int val : map.values()) {
+                result += val * (val - 1);
+            }
+            map.clear();
+        }
+        return result;
+    }
+
+    private long calcDistance(int[] p1, int[] p2) {
+        long x = p2[0] - p1[0];
+        long y = p2[1] - p1[1];
+        return x * x + y * y;
+    }
+
+    public static void main(String... args) {
+        NumberofBoomerangs test = new NumberofBoomerangs();
+        // int[][] points = new int[][]{
+        // {0,0},
+        // {1,0},
+        // {2,0},
+        // };
+
+        // [[3,6],[7,5],[3,5],[6,2],[9,1],[2,7],[0,9],[0,6],[2,6]], should return 10
+        int[][] points = new int[][] { { 3, 6 }, { 7, 5 }, { 3, 5 }, { 6, 2 }, { 9, 1 }, { 2, 7 },
+                { 0, 9 }, { 0, 6 }, { 2, 6 }, };
+
+        // [[0,0],[1,0],[-1,0],[0,1],[0,-1]] should return 20
+        System.out.println(test.numberOfBoomerangs(points));
+    }
+}
diff --git a/README.md b/README.md
@@ -2,6 +2,7 @@
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
 |453|[Minimum Moves to Equal Array Elementss](https://leetcode.com/problems/minimum-moves-to-equal-array-elements/)|[Solution](../../blob/master/EASY/src/easy/MinimumMovestoEqualArrayElements.java)| O(n)|O(n) | Easy| BFS
+|447|[Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/)|[Solution](../../blob/master/EASY/src/easy/NumberofBoomerangs.java)| O(n^2)|O(n) | Easy|
 |441|[Arranging Coins](https://leetcode.com/problems/arrange-coins/)|[Solution](../../blob/master/EASY/src/easy/ArrangingCoins.java)| O(n)|O(1) | Easy|
 |419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../../blob/master/MEDIUM/src/medium/BattleshipsinaBoard.java) | O(n^2) |O(1) | Medium| DFS
 |417|[Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)|[Solution](../../blob/master/MEDIUM/src/medium/PacificAtlanticWaterFlow.java) | O(m*n*Max(m,n)) |O(m*n) | Medium| DFS
