[LeetCode] Number of Boomerangs

Problem: You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. A boomerang is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters). Return the number of boomerangs.

Example:

Input: points = [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Input: points = [[1,1],[2,2],[3,3]]
Output: 2

Input: points = [[1,1]]
Output: 0

Approach: This problem is straight forward to solve. Basically we take every point in points one by one and calculate it's distance from every other point. Whenever we got number of points >= 2 for a particular distance, we know that we get nP2(order does matter) boomerangs. We can use hashing to maintain number of points for a particular distance.

Implementation in C#:

        public int NumberOfBoomerangs(int[][] points)

        {

            int result = 0;

            for(int i = 0; i < points.Length; ++i)

            {

                Dictionary<int, int> distances = new Dictionary<int, int>();

                for (int j = 0; j < points.Length; ++j)

                {

                    if (i != j)

                    {

                        int distance = (int)(Math.Pow(points[j][0] - points[i][0], 2) + Math.Pow(points[j][1] - points[i][1], 2));

                        if (!distances.ContainsKey(distance))

                        {

                            distances.Add(distance, 0);

                        }

                        ++distances[distance];

                    }

                }

                foreach(int distance in distances.Keys)

                {

                    int count = distances[distance];

                    result += count * (count - 1);

                }

            }

            return result;

        }

Complexity: O(n^2)