Number of Boomerangs
MedPrompt
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: 2Example 3:
Input: points = [[1,1]]
Output: 0
Constraints:
n == points.length1 <= n <= 500points[i].length == 2-104 <= xi, yi <= 104- All the points are unique.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through all possible combinations of three distinct points (i, j, k) and checking if they form a boomerang. A boomerang is defined by the condition that the distance from point i to j is equal to the distance from point i to k.
Algorithm
- Initialize a counter
countto 0. - Use three nested loops to iterate through all unique triplets of indices
(i, j, k). - For each triplet, calculate the squared distance between
points[i]andpoints[j], and the squared distance betweenpoints[i]andpoints[k]. - If the two distances are equal, increment the
count. - After checking all triplets, return
count.
Walkthrough
This approach directly translates the problem definition into code. We check every possible ordered triplet of distinct points (i, j, k) to see if it satisfies the boomerang condition: distance(i, j) == distance(i, k). To avoid floating-point precision issues and the performance cost of square roots, we compare the squared distances instead. The squared distance between two points (x1, y1) and (x2, y2) is (x1 - x2)^2 + (y1 - y2)^2. The implementation involves three nested loops to select the three points, followed by a check for the distance equality.
class Solution { public int numberOfBoomerangs(int[][] points) { int n = points.length; if (n < 3) { return 0; } int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; for (int k = 0; k < n; k++) { if (i == k || j == k) continue; long dist_ij = getSquaredDistance(points[i], points[j]); long dist_ik = getSquaredDistance(points[i], points[k]); if (dist_ij == dist_ik) { count++; } } } } return count; } private long getSquaredDistance(int[] p1, int[] p2) { long dx = p1[0] - p2[0]; long dy = p1[1] - p2[1]; return dx * dx + dy * dy; }}Complexity
Time
O(n^3), where n is the number of points. We have three nested loops, each iterating up to n times. This makes the approach very slow for larger inputs.
Space
O(1). We only use a few variables to store indices and the count, so the extra space required is constant.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient due to the cubic time complexity.
Likely to result in a 'Time Limit Exceeded' error for the given constraints (n <= 500).
Solutions
Solution
class Solution { public int numberOfBoomerangs ( int [][] points ) { int ans = 0 ; for ( int [] p1 : points ) { Map < Integer , Integer > cnt = new HashMap <>(); for ( int [] p2 : points ) { int d = ( p1 [ 0 ] - p2 [ 0 ]) * ( p1 [ 0 ] - p2 [ 0 ]) + ( p1 [ 1 ] - p2 [ 1 ]) * ( p1 [ 1 ] - p2 [ 1 ]); cnt . merge ( d , 1 , Integer: : sum ); } for ( int x : cnt . values ()) { ans += x * ( x - 1 ); } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.