Number of Boomerangs

MEDIUM

Description

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

Checkout 2 different approaches to solve Number of Boomerangs. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1). We only use a few variables to store indices and the count, so the extra space required is constant.

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Number of Boomerangs. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Number of Boomerangs

Patterns:

Math

Data Structures:

ArrayHash Table