You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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).
Return the number of boomerangs.
Example 1:
Input: points = [[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]].
Example 2:
Input: points = [[1,1],[2,2],[3,3]] Output: 2
Example 3:
Input: points = [[1,1]] Output: 0
Constraints:
n == points.length1 <= n <= 500points[i].length == 2-104 <= xi, yi <= 104This approach involves treating each point as a base point and calculating the distance to all other points. A hashmap (or dictionary) is used to count occurrences of each distance. For any two points that share the same distance to the base point, we have two boomerangs.
We use a fixed-size array `dist` to store the count of distances from the base point to all other points. For each pair of points with the same distance, two boomerangs can be formed. The array `dist` is reset on every iteration to count new distances for the next base point.
C++
Java
Python
C#
JavaScript
Time complexity is O(n^2) where n is the number of points, and space complexity is O(SIZE) for the distance count array.
This approach involves using a lookup table to pre-compute square distance values. This can reduce some computational overhead during the distance calculation step by avoiding repetitive arithmetic operations.
In this implementation, a static array `dist` is used to store pre-computed square distances for efficient access. The cost of setting up the lookup table is offset by faster access during distance retrieval.
C++
Java
Python
C#
JavaScript
Time complexity remains O(n^2), but the space complexity is larger due to the MAX_DIST array.
| Approach | Complexity |
|---|---|
| Approach 1: Distance Counting using HashMap | Time complexity is O(n^2) where n is the number of points, and space complexity is O(SIZE) for the distance count array. |
| Approach 2: Pre-computation and Lookup Table | Time complexity remains O(n^2), but the space complexity is larger due to the MAX_DIST array. |
How to EASILY solve LeetCode problems • NeetCode • 427,689 views views
Watch 9 more video solutions →Practice Number of Boomerangs with our built-in code editor and test cases.
Practice on FleetCode