447.Number of Boomerangs

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

Count distance

Runtime 137ms		Memory 45.36MB

[math]\displaystyle{ C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!} }[/math]

[math]\displaystyle{ P(n,r) = \frac{n!}{(n-r)!} }[/math]

P(n,2)=n * (n -1) * (n - 2) ...* 2 * 1/(n - 2) ...* 2 * 1=n * (n-1)

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int sum = 0;
        for(int i = 0; i < points.length; i++) {
            Map<Integer, Integer> counts = new HashMap<>();
            for(int j = 0; j < points.length; j++) {
                if( i == j) continue;
                int dij = distance(points, i, j);
                int count = counts.getOrDefault(dij, 0);
                count ++;
                counts.put(dij, count);
            }
            for(int count: counts.values()) {
                sum += count * (count -1);
            }
        }
        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;
    }
}

Count distance optimized

Runtime 92ms		Memory 76.8MB

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int sum = 0;
        Map<Integer, Integer> counts = new HashMap<>();
        for(int i = 0; i < points.length; i++) {
            for(int j = 0; j < points.length; j++) {
                if( i == j) continue;
                int dij = distance(points, i, j);
                counts.put(dij, counts.getOrDefault(dij, 0) + 1);
            }
            for(int count: counts.values()) {
                sum += count * (count -1);
            }
            counts.clear();
        }
        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;
    }
}