algoadvance

The problem, Number of Boomerangs (LeetCode 447), is as follows:

Given n points in the plane that are all pairwise distinct, 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).

You need to return the number of boomerangs.

Example:

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

Clarifying Questions

1. Are the points guaranteed to be distinct?
   • Yes, the problem states that the points are all pairwise distinct.
2. What should we return if there are fewer than 3 points?
   • Return 0 because it’s not possible to form a boomerang with fewer than 3 points.

Strategy

1. Distance Calculation: Use the squared Euclidean distance between points to avoid floating-point precision issues.
2. Hash Map Usage: For each point, create a hash map to store the count of other points at each possible distance from the current point.
3. Count Boomerangs: For each distance with more than one point, add to the count the number of boomerangs that can be formed with the current point as the pivot.
4. Iterate over each point and use the distances hash map to count boomerangs for that point.

Code

def numberOfBoomerangs(points):
    from collections import defaultdict

    def get_distance(p1, p2):
        return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

    boomerangs_count = 0

    for i in range(len(points)):
        distance_map = defaultdict(int)
        for j in range(len(points)):
            if i == j:
                continue
            distance = get_distance(points[i], points[j])
            distance_map[distance] += 1

        for distance, count in distance_map.items():
            if count > 1:
                boomerangs_count += count * (count - 1)

    return boomerangs_count

Time Complexity

• Distance Calculation: O(1) for each pair of points.
• Loop Over Points: Each point is considered as a pivot once.
• Overall Complexity: O(n^2), where n is the number of points. This is because for each of the n points, we compute distances to the other n-1 points, accumulating results in a hash map, which results in O(n) operations per point.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?