Clean java solution: O(n^2) 166ms


  • 80
    A
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
    
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<points.length; i++) {
            for(int j=0; j<points.length; j++) {
                if(i == j)
                    continue;
                
                int d = getDistance(points[i], points[j]);                
                map.put(d, map.getOrDefault(d, 0) + 1);
            }
            
            for(int val : map.values()) {
                res += val * (val-1);
            }            
            map.clear();
        }
        
        return res;
    }
    
    private int getDistance(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];
        
        return dx*dx + dy*dy;
    }
    
    Time complexity:  O(n^2)
    Space complexity: O(n)

  • 4
    R

    @asurana28 I understand the code, but could you please tell me why are we doing the val * (val-1) ? I am not able to wrap my head around it.

    is it the number of permutations with 2 points ? I am not able to understand. Please explain.


  • 1
    B

    @RepentThySins Yes, you already know the answer :)


  • 0
    A

    @asurana28: Awesome solution!


  • 25
    A

    @RepentThySins

    For every i, we capture the number of points equidistant from i. Now for this i, we have to calculate all possible permutations of (j,k) from these equidistant points.

    Total number of permutations of size 2 from n different points is nP2 = n!/(n-2)! = n * (n-1). hope this helps.


  • 6

    Very clever that you do not use the actual distance. I used Math.sqrt(), and HashMap<Double, Integer>, which is found to be totally unnecessary.


  • 7
    A

    @chidong
    Using square of actual distance helps in two ways:

    1. Performance: we don't have to do extra step of taking square root
    2. Accuracy: we can end up having same square root values for two large consecutive numbers because of the precision limitation of data-types float/double.

  • 0
    J

    @asurana28 thanks for your explaintation


  • 0
    V

    Is this really 166ms? Mine is same logic in C++ and it's giving me 1660ms :(


  • 0
    A

    @vishal51 I did few runs and it was around 170ms for me. You can try submitting the same code.
    Optimizations beyond big-O will require language specific optimizations. Like I used map.clear() instead of creating a new instance of HashMap inside the outer loop to avoid the penalty of object creation every time it enters outer loop.


  • 0
    V

    @asurana28 Do you see any difference, last time I ran this gave me 1540ms...terrible !

    class Solution {
        inline int dist(pair<int, int>& p1, pair<int, int>& p2) {
            int dx = p1.first - p2.first;
            int dy = p1.second - p2.second;
            return dx * dx + dy * dy;
        }
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            map<int, int> m;
            int ans = 0;
            for (auto p1 : points) {
                for (auto p2 : points)
                    m[dist(p1, p2)]++;
                for (auto entry : m)
                    ans += entry.second * (entry.second - 1);
                m.clear();
            }
            return ans;
        }
    };
    

  • 3
    A

    @vishal51
    Better to use unordered_map instead of map in c++; your code's time_complexity degraded to O(n^2 * logn) because of map.

    • map (c++) is implemented using BST - get/set are log(n) operations
    • unordered_map (c++) is implemented as hashtable - get/set are O(1) operations

  • 0
    L

    Brilliant! it's 151ms using my computer.
    You are here!
    Your runtime beats 95.65% of java submissions.


  • 0
    C

    From point i to point j, getDistance() is called; from point j to point i, getDistance() is called again for the same pair. So at least one of the calculation is not neccessary.


  • 0
    A

    @czhangaegean
    This calculation is unavoidable.
    Lets say the distance between i and j is d. The number of points (including j) at distance d from i could be different from the number of points (including i) at distance d from j. Thus the total number of permutations for i and j with distance d could be different.


  • 0
    M

    @vishal51
    you can google "difference between map and unordered_map"


  • 0
    K

    Could you please explain why the complexity is O(n^2)?
    I read the code and I think the time complexity is O(n^3).


  • 2
    A

    @kawayikp
    Outer loop runs n times. Both inner loops also run n times, and the statements inside both inner loops are O(1).

    Time complexity = O(n * 2n * 1) = O(n^2)


  • 0
    K

    @asurana28
    Yes, your are right! Thanks.


  • 0
    J

    Brilliant! And getOrDefault() from java 8 is concise! Thanks for your sharing!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.