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


  • 3

    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;
        }
    

  • 0
    M

    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.


  • 0

    @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.


  • 0
    M

    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)
    
    

  • 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.


Log in to reply
 

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