Number Of Boomerangs - Leetcode Solution

Problem Statement:

Given an array of points, a boomerang is a set of three points (i, j, k) where the distance between i and j is the same as the distance between i and k (the order of the points matters).

Input: [[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]]

Solution:

One approach to solve this problem is to use a brute force method by iterating through all the points and for every point, calculate the distances to all other points. Then, we can check if any two points have the same distance from the current point. If they do, then we have found a boomerang. We can count the number of such boomerangs and return the count at the end.

However, this approach has a time complexity of O(n^3) as we are iterating through the array three times. This is not a very efficient approach and can lead to a time limit exceeded error for larger test cases.

A more optimized solution is to use a hashmap to store the distances between each point and all other points. We can then iterate through the hashmap and for each point, check if any other point has the same distance as it from the current point. If there are m points that have the same distance from the current point, then there are m*(m-1) boomerangs that can be formed with the current point.

We can keep track of the count of boomerangs formed for each point and add them to a total count. At the end, we can return the total count.

Here's the Python code for the optimized solution:

class Solution: def numberOfBoomerangs(self, points: List[List[int]]) -> int: count = 0

    for i in range(len(points)):
        # create a hashmap to store the distances from the current point
        dist_map = {}
        
        for j in range(len(points)):
            if i == j:
                continue
            
            # calculate the distance between the current point and all other points
            dist = pow(points[j][0]-points[i][0], 2) + pow(points[j][1]-points[i][1], 2)
            
            # add the distance to the hashmap
            if dist in dist_map:
                dist_map[dist] += 1
            else:
                dist_map[dist] = 1
        
        # calculate the number of boomerangs that can be formed with the current point
        for dist in dist_map:
            count += dist_map[dist] * (dist_map[dist]-1)
    
    return count

The time complexity of this approach is O(n^2) which is much more efficient than the brute force approach.

1