Leetcode Number of Boomeranges problem solution

by

In this Leetcode Number of Boomerangs problem solution, 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.

Leetcode Number of Boomeranges problem solution

Problem solution in Python.

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        count = 0
        for i in range(len(points)):
            dt_dict = dict()
            for j in range(len(points)):
                if j != i:
                    dt = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2)
                    count += dt_dict.get(dt, 0)
                    dt_dict[dt] = dt_dict.get(dt, 0) + 1
        return count * 2

Problem solution in Java.

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        Map<Double,Integer> map = new HashMap<>();
        int res = 0 ;
        for(int i = 0 ; i < points.length ; i++){
            for(int j = 0 ; j < points.length ; j++){
                if(i==j) continue;
                double tmp = getDis(points[i],points[j]);
                map.put(tmp,map.getOrDefault(tmp,0)+1);
            }
            for(double x : map.keySet())
                res += map.get(x)*(map.get(x)-1);
            map.clear();
        }
        return res;
    }
    public double getDis(int[] x , int[] y){
        return (x[0]-y[0])*(x[0]-y[0]) + (x[1]-y[1])*(x[1]-y[1]);
    }
}

Problem solution in C++.

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int result=0;
        unordered_map<int,int> mp;
        for(int i=0;i<points.size();i++){
            int x1=points[i].first;
            int y1=points[i].second;
            for(int j=0;j<points.size();j++){
                int x2=points[j].first;
                int y2=points[j].second;
                int dis=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
                mp[dis]++;
            }
            for(unordered_map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
                if((*it).second>1)result+=((*it).second)*((*it).second-1);
            mp.clear();
        }
        return result;
    }    
};

Problem solution in C.

#define MAP_SIZE 500

struct HashMap
{
    int count;
    int val;
    struct HashMap *next;
} disHashMap[MAP_SIZE];


void addToHashMap(int key) {
    int slot = key % MAP_SIZE;
    struct HashMap *p;

    if (disHashMap[slot].val == key) {
        disHashMap[slot].count++;
    } else if (disHashMap[slot].val == 0) {
        disHashMap[slot].val = key;
        disHashMap[slot].count++;
    } else {
        p = &disHashMap[slot];

        while (p->val != key && p->next != NULL) {
            p = p->next;
        }

        if (p->val == key) {
            p->count++;
        } else {
            p->next = (struct HashMap *)malloc(sizeof(struct HashMap));
            p = p->next;
            p->val = key;
            p->count = 1;
            p->next = NULL;
        }
    }

}

int getDistance(int* a, int *b) {
    return abs(a[0] - b[0]) * abs(a[0] - b[0]) + abs(a[1] - b[1]) * abs(a[1] - b[1]);
}

int numberOfBoomerangs(int** points, int pointsRowSize, int pointsColSize) {
    int i, j, k;
    int ret = 0;

    struct HashMap *p, *toBeFree, *next;

    for (i = 0; i < pointsRowSize; i++) {

        for (k = 0; k < MAP_SIZE; k++) {
            disHashMap[k].val = 0;
            disHashMap[k].count = 0;
            disHashMap[k].next = NULL;
        }

        for (j = 0; j < pointsRowSize; j++) {
            if (i == j) {
                continue;
            }

            addToHashMap(getDistance(points[i], points[j]));
        }

        for (k = 0; k < MAP_SIZE; k++) {
            p = &disHashMap[k];

            while (p != NULL) {
                if (p->count > 1) {
                    ret += p->count * (p->count - 1);
                }
                p = p->next;
            }
        }

    }

    return ret;
}