Valid Boomerang - Leetcode Solution

Problem Statement:

A boomerang is a set of 3 points that are all distinct and not in a straight line.

Given an array of points in the plane, return the number of boomerangs.

Example: 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:

To solve this problem, we need to iterate through each point in the array and calculate the distance from that point to all other points. We can store the distances in a dictionary or a hashmap, where the keys are the distances and the values are the counts of points that are at that distance from the current point.

Next, we can count the number of boomerangs that we can form using the current point as the middle point. We can do this by iterating through the distances in the dictionary and for each distance, we can calculate the number of boomerangs that we can form using the points that are at that distance from the current point.

This can be done using the formula n*(n-1), where n is the count of points at that distance from the current point. We need to multiply this by 2, because we can form two boomerangs using the current point as the middle point.

Finally, we can add the count of boomerangs formed using the current point to the total count of boomerangs and move on to the next point.

Here's the Python code that implements the above algorithm:

def numberOfBoomerangs(points): count = 0 for i in range(len(points)): distances = {} for j in range(len(points)): if i == j: continue d = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2 distances[d] = distances.get(d, 0) + 1

    for d in distances:
        n = distances[d]
        count += n*(n-1)*2

return count

Time Complexity: O(n^2), where n is the number of points in the array. We need to calculate the distances between every pair of points, which takes O(n^2) time.

Space Complexity: O(n), for storing the distances in the dictionary. The space required for the output and intermediate variables is negligible compared to this.

1