Share my straightforward solution with HashMap, O(N^2)


  • 20

    The idea is simple, for every point, we aggregate points with the same distance and put them in a Set.

    Update:

    I got this solution during the contest, and as troy351 said, Actually we don't need Map<Integer, Set>, and Map<Integer, Integer> is enough.

    public class Solution {
        public int numberOfBoomerangs(int[][] points) {
            if(points.length==0 || points[0].length==0) return 0;
            int ret = 0;
            for(int i=0;i<points.length;i++){
                Map<Integer, Set<int[]>> map = new HashMap<>();
                int[] p = points[i];
                for(int j=0;j<points.length;j++){
                    if(j==i) continue;
                    int[] q = points[j];
                    int dis = getDis(p, q);
                    if(!map.containsKey(dis)) map.put(dis, new HashSet<int[]>());
                    map.get(dis).add(q);
                }
                for(Integer key : map.keySet()){
                    int size = map.get(key).size();
                    if(size>=2) ret += (size*(size-1));
                }
            }
            return ret;
        }
        public int getDis(int[] p, int[] q){
            int a = p[0]-q[0];
            int b = p[1]-q[1];
            return a*a+b*b;
        }
    }
    

  • 0
    A

    similar idea but clean and efficient solution @https://discuss.leetcode.com/topic/66587/clean-java-solution-o-n-2-166ms


  • 4
    T
    • In function getDis, there is no need to distinguish which is greater, for the square of a number must be positive.
    • Also, there is no need to save the specific points use a HashSet, because we just want to know how many points are there, and we don't care about what are they exactly.

  • 0
    B
    This post is deleted!

  • 1
    W

    Great solution! Two notes:

    1. When you find a dis occurring twice or more, you can add it to a multiple occurring key hashset, so you don't need to go over all the keys in the map when you're building the sum, just the keys in the hashset.

    2. Great idea to ignore getting the sqrt of the sum of the squares! I was using a double as my key because I was doing the sqrt and hit a Memory Limit Exceeded error, but once I stopped using sqrt, I no longer needed to use double as my key and could use int, which let me stay within memory bounds.


  • 3
    // for each point, store the distance from all other points to it and group points with same distance.
    // as we only need the number, so we just store number instead of actually points.
    public int numberOfBoomerangs(int[][] points) {
          Map<Integer,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;
        		int d = distance(points[i],points[j]);
        		map.put(d, map.getOrDefault(d, 0) + 1);
        	}
        
        
          for(int val : map.values()) {
               res += val * (val-1); // k * (k - 1) possibilities
          }            
          map.clear();
        }
        return res;	
    }
    
    
        private int distance(int[] a, int[] b){
        	int dx = a[0] - b[0];
        	int dy = a[1] - b[1];
        	return dx * dx + dy * dy;
        }

  • 1
    G

    rewrite in java :--)

    	public static int numberOfBoomerangs(int [][]points){
    		int count=0;
    		Map<Integer,Integer>map=new HashMap<Integer,Integer>();
    		for(int i=0;i!=points.length;i++){
    			for(int j=0;j!=points.length;j++){
    				if(i==j){
    					continue;
    				}
    				//calculate distance
    				int deltax=points[i][0]-points[j][0];
    				int deltay=points[i][1]-points[j][1];
    				int square=deltax*deltax+deltay*deltay;
    				if(map.containsKey(square)){
    					map.put(square, map.get(square)+1);
    				}else{
    					map.put(square,1);
    				}
    			}
    			for(int value:map.values()){//2*C(n,2)
    				count+=value*(value-1);
    			}
    			map.clear();
    		}
    
    		return count;
    	}

  • 0

    @YuTingLiu
    Thanks for your straightforward solution, I think there's still two more things to improve performance.

    1. Since every component in this points is distinct, we can directly count repeated distance times for each component, so map<Integer, Integer> is enough for this question.
    2. Traverse HashMap to count result is also unnecessary, we can directly count result once finding same distance goes like this: result += map.get(distance) * 2;
      which can be extended as: result += (map.get(distance) + 1) * map.get(distance) - map.get(distance) * (map.get(distance) - 1);

  • 0
    Y

    good idea............


  • 0

    I don't understan why result+=size*(size-1)


  • 0
    T

    @妙手屠夫SYAU
    Permutation
    take 2 from n elements (order matters), there are total P(2, n) = n! / (n-2)! = n * (n-1) possible solutions


Log in to reply
 

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