# C# - HashTable solution O(n^2) time, O(n) space with explaination

• Foreach point, call this a center point, group the other points into buckets where each bucket contains points that are the same distance from the center point. Each bucket with more than 1 point can make boomerangs.

How many boomerangs can a bucket make?

Each point in a bucket can make a boomerang with all other points in the bucket. A bucket with N points, can make N * (N - 1) boomerangs.

``````    public int NumberOfBoomerangs(int[,] points)
{
int n = points.GetLength(0);
int count = 0;

for (int p0 = 0; p0 < n; p0++)
{
// Keep a lookup of the distance from p0 to all other points
// if you find another point with same distance give that distance
// a count of 1 (one other point), if you see another point of this
// distance move count to 2 and so on.
Dictionary<int,int> distSqMap = new Dictionary<int,int>();
for (int p1 = 0; p1 < n; p1++)
{
if (p1 == p0) continue;

// avoid square root calculation - do distance check against distance square
int distSq = (points[p0,0] - points[p1,0])*(points[p0,0] - points[p1,0])
+ (points[p0,1] - points[p1,1])*(points[p0,1] - points[p1,1]);

if (!distSqMap.ContainsKey(distSq))
{
distSqMap[distSq] = 0;
}
else
{
distSqMap[distSq]++;
}
}

// count number of combinations for groups of equally distanced points
foreach (int groupCount in distSqMap.Values)
{
count += groupCount * (groupCount + 1);
}
}

return count;
}
``````

• Great solution! Thank you, Jdrogin.

I probably spent more than 4 hours on this problem today, and although I got close to your solution, I didn't quite nail it.

If possible, would you be so kind as to explain what is happening here:

``````groupCount * (groupCount + 1)
``````

I mean, I understand the code, but I don't understand why you would write that particular equation. If you could provide an intuitive explanation, I'd be much obligued.

• @mclachlan sure, here is some more explaination

Foreach point, call this a center point, group the other points into buckets were each bucket contains points that are the same distance from the center point. Each bucket with more than 1 point can make boomerangs.

How many boomerangs can a bucket make?

Each point in a bucket can make a boomerang with all other points in the bucket. A bucket with N points, can make N * (N - 1) boomerangs.

• Thanks for the reply, @jdrogin.

How many boomerangs can a bucket make?

Each point in a bucket can make a boomerang with all other points in the bucket.

This is where I get lost. No, wait... I get it!!

OK! So for every point in the bucket (N), they can connect with every other point (N - 1); therefore N * (N - 1).

Thanks a lot, man... or woman, as the case may be. I really appreciate you taking some time to help me out.

Best wishes.

For those that don't understand how groupCount * (groupCount + 1) became N * (N - 1):
@jdrogin's algorithm actually sets groupCount to zero for the first point, 1 for the second point, etc. So, if N == groupCount + 1

``````N * (N - 1)
== (groupCount + 1) * ((groupCount + 1) - 1)
== (groupCount + 1) * (groupCount)
== groupCount * (groupCount + 1)

``````

• yes, my counting is probably not as straight forward as it could have been. But the idea is the same, group them by distance to a center point and use the count and the logic outlined to get the result.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.