Description

	#447	Number of Boomerangs	Medium
		unknown	Top 150
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).

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

Solution

Brute force

Runtime 799ms

Memory 40.97MB

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int sum = 0;
        for(int i = 0; i < points.length; i++) {
            for(int j = i + 1; j < points.length; j++) {
                for( int k = j + 1; k < points.length; k++) {
                    if(distance(points, i, j) == distance(points, i, k))
                        sum += 2;
                    if(distance(points, j, i) == distance(points, j, k))
                        sum += 2;
                    if(distance(points, k, i) == distance(points, k, j))
                        sum += 2;
                }
            }
        }
        return sum;
    }

    private static int distance(int[][] points, int i, int j) {
        int l =  points[i][0] - points[j][0];
        int w =  points[i][1] - points[j][1];
        return l * l + w * w;
    }
}