Simple Java Solution using HashMap, beats 90%


  • 5

    Idea is to add the distance between point i and point j in a HashMap and keep checking the value. Trick is to keep incrementing the value when you will find distance equal to key. It will take care of all the combinations possible. Also as [a,b,c] and [a,c,b]are two different cases we need to multiply count by 2.

    public int numberOfBoomerangs(int[][] p) {
            int n = p.length;
            if(n==0) return 0;
            int count = 0;
            for(int i=0;i<n;i++){
                Map<Double,Integer> map = new HashMap<>();
                for(int j=0;j<n;j++){
                    if(map.containsKey(distance(p[i],p[j]))){
                        int value = map.get(distance(p[i],p[j]));
                        count+=2*value;
                        map.put(distance(p[i],p[j]),value+1);
                    } else {
                        map.put(distance(p[i],p[j]),1);
                    }
                }
            }
            return count;
        }
        
        public Double distance(int[] a, int[]b){
            return Math.sqrt(Math.pow(a[0]-b[0],2) + Math.pow(a[1]-b[1],2));
        }```

  • 0

    you can speed your code by replace distance(p[i],p[j]) with a variable.
    Something like this:

    				double distance = distance(points[i], points[j]);
    				if(map.containsKey(distance)){
    					int value = map.get(distance);
    					count+= value*2 ;
    					map.put(distance, value+1);
    				}
    				else
    				{
    					map.put(distance, 1);
    				}
    			}```

  • 0
    L

    great!!!!!!!!!!!!!


  • 3
    G

    Great idea!
    I rewrote your solution to few faster version

        public int numberOfBoomerangs(int[][] p) {
            int count = 0;
            Map<Integer,Integer> map = new HashMap<>(p.length);
            for(int[] i: p){
                for(int[] j: p){
                    int dx=i[0]-j[0];
                    int dy=i[1]-j[1];
                    int d = dx*dx+dy*dy;
                    Integer value = map.get(d);
                    if(value!=null){
                        count+=2*value;
                        map.put(d,value+1);
                    } else 
                        map.put(d,1);
                }
                map.clear();
            }
            return count;
        }
    

  • 0

    Thanks for sharing, very clever solution. Also thanks to @gorokhovsky for the optimization. I tried it and the two optimizations cut the running time from 251ms to 112ms(currently 99.56% 2017-06-28 23:22:56) on my machine.


Log in to reply
 

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