447. Number of Boomerangs

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int numberOfBoomerangs(vector>& points) { int ans = 0; for (const vector& p : points) { unordered_map distCount; for (const vector& q : points) { const int dist = getDist(p, q); ++distCount[dist]; } for (const auto& [_, freq] : distCount) ans += freq * (freq - 1); // C(freq, 2) } return ans; } private: int getDist(const vector& p, const vector& q) { return pow(p[0] - q[0], 2) + pow(p[1] - q[1], 2); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int numberOfBoomerangs(int[][] points) { int ans = 0; for (int[] p : points) { Map distCount = new HashMap<>(); for (int[] q : points) { final int dist = (int) getDist(p, q); distCount.put(dist, distCount.getOrDefault(dist, 0) + 1); } for (final int freq : distCount.values()) ans += freq * (freq - 1); // C(freq, 2) } return ans; } private double getDist(int[] p, int[] q) { return Math.pow(p[0] - q[0], 2) + Math.pow(p[1] - q[1], 2); } } 
  1 2 3 4 5 6 7 8 9 10 11 class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int: ans = 0 for x1, y1 in points: count = collections.defaultdict(int) for x2, y2 in points: ans += 2 * count[(x1 - x2)**2 + (y1 - y2)**2] count[(x1 - x2)**2 + (y1 - y2)**2] += 1 return ans