Leetcode 0447 Number of Boomerangs

Problem statement

https://leetcode.com/problems/number-of-boomerangs/

Solution

For each point keep hash table of distances between this point and all others: $s_1,\dots, s_k$ and add $s_1(s_1-1) + \dots s_k(s_k-1)$ to total number of boomerangs.

Complexity

Time complexity is O(n^2), space complexity is O(n).

Code

class Solution:
    def numberOfBoomerangs(self, P):
        n, ans = len(P), 0
        for i in range(n):
            dists = Counter([(P[j][0] - P[i][0])**2 + (P[j][1] - P[i][1])**2 for j in range(n)])
            ans += sum(i*(i-1) for i in dists.values())
            
        return ans