Number of Boomerangs

Med

#0434Time: 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.

Patterns

Math

Data structures

Array Hash Table

Prompt

You are given n points in the plane that are all distinct, where points[i] = [x_i, y_i]. 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.length
1 <= n <= 500
points[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
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 count to 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] and points[j], and the squared distance between points[i] and points[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.

1class Solution {2    public int numberOfBoomerangs(int[][] points) {3        int n = points.length;4        if (n < 3) {5            return 0;6        }7        int count = 0;8        for (int i = 0; i < n; i++) {9            for (int j = 0; j < n; j++) {10                if (i == j) continue;11                for (int k = 0; k < n; k++) {12                    if (i == k || j == k) continue;13                    14                    long dist_ij = getSquaredDistance(points[i], points[j]);15                    long dist_ik = getSquaredDistance(points[i], points[k]);16                    17                    if (dist_ij == dist_ik) {18                        count++;19                    }20                }21            }22        }23        return count;24    }25 26    private long getSquaredDistance(int[] p1, int[] p2) {27        long dx = p1[0] - p2[0];28        long dy = p1[1] - p2[1];29        return dx * dx + dy * dy;30    }31}

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).

A more efficient approach is to iterate through each point and consider it as the pivot of a potential boomerang. For each pivot point, we can use a hash map to count how many other points are at the same distance from it. This avoids the third loop of the brute-force method.

Algorithm

Initialize totalBoomerangs = 0.
Iterate through each point p_i to serve as the pivot.
For each pivot p_i, create a HashMap to store frequencies of distances to other points.
Iterate through all other points p_j and populate the map with (squared_distance, count).
After populating the map, iterate through its values (m).
For each count m, add m * (m - 1) to totalBoomerangs.
After iterating through all pivots, return totalBoomerangs.

Walkthrough

We can significantly optimize the process by changing our perspective. Instead of checking every triplet, we can fix one point i as the pivot and then find how many pairs (j, k) exist that are equidistant from i. A hash map is the perfect tool for this.

For each point i, we iterate through all other points j, calculate the squared distance d between i and j, and store these distances in a hash map. The map will have the distance d as the key and the number of points at that distance as the value.

Once the map is built for pivot i, we can iterate through it. If m points are found at a certain distance, we know we can form m * (m - 1) boomerangs. This is a permutation calculation (P(m, 2)), as we need to choose an ordered pair of two distinct points from the m available points to be j and k. We sum these counts for all distances and all pivots to get the final answer.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int numberOfBoomerangs(int[][] points) {6        int totalBoomerangs = 0;7        int n = points.length;8        9        for (int i = 0; i < n; i++) {10            Map<Long, Integer> distanceMap = new HashMap<>();11            12            for (int j = 0; j < n; j++) {13                if (i == j) {14                    continue;15                }16                17                long dist = getSquaredDistance(points[i], points[j]);18                distanceMap.put(dist, distanceMap.getOrDefault(dist, 0) + 1);19            }20            21            for (int count : distanceMap.values()) {22                totalBoomerangs += count * (count - 1);23            }24        }25        26        return totalBoomerangs;27    }28 29    private long getSquaredDistance(int[] p1, int[] p2) {30        long dx = p1[0] - p2[0];31        long dy = p1[1] - p2[1];32        return dx * dx + dy * dy;33    }34}

Complexity

Time

O(n^2), where n is the number of points. The outer loop runs n times (for each pivot). The inner loop also runs n times to calculate distances and populate the hash map. This is a significant improvement over the brute-force approach.

Space

O(n). For each pivot point, we use a hash map to store distances. In the worst-case scenario, all other n-1 points are at distinct distances from the pivot, so the map will store n-1 entries.

Trade-offs

Pros

Much more efficient with a quadratic time complexity.
Passes the time limits for the given constraints.

Cons

Uses extra space for the hash map.

Solutions

Solution

1class 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 ; } }

1class Solution { public: int numberOfBoomerangs ( vector < vector < int >>& points ) { int ans = 0 ; for ( auto & p1 : points ) { unordered_map < int , int > cnt ; for ( auto & p2 : points ) { int d = ( p1 [ 0 ] - p2 [ 0 ]) * ( p1 [ 0 ] - p2 [ 0 ]) + ( p1 [ 1 ] - p2 [ 1 ]) * ( p1 [ 1 ] - p2 [ 1 ]); cnt [ d ] ++ ; } for ( auto & [ _ , x ] : cnt ) { ans += x * ( x - 1 ); } } return ans ; } };

1class Solution : def numberOfBoomerangs ( self , points : List [ List [ int ]]) -> int : ans = 0 for p1 in points : cnt = Counter () for p2 in points : d = dist ( p1 , p2 ) cnt [ d ] += 1 ans += sum ( x * ( x - 1 ) for x in cnt . values ()) 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.

← Previous

Previous problem

Next problem