Why TLE? Thanx!


  • 0
    N

    I think this is also O(n^2), The idea is the same, for each point, each distance, store the number of integers. Can anyone tell me why this get TLE?

        public int numberOfBoomerangs(int[][] points) {
            Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
            for (int i = 0; i < points.length; i++) { //O(n)
                map.put(i, new HashMap<>());
                for (int j = 0; j < points.length; j++) {//O(n)
                    if (j == i) continue;
                    int distance = (int)(Math.pow(points[i][0] - points[j][0], 2) + Math.pow(points[i][1] - points[j][1], 2));
                    if(!map.get(i).containsKey(distance)) {
                        map.get(i).put(distance, 0);
                    }
                    map.get(i).put(distance, map.get(i).get(distance) + 1);
                }
            }
            int count = 0;
            for (int key1 : map.keySet()) {
                for (int key2 : map.get(key1).keySet()) {
                    count += map.get(key1).get(key2) * (map.get(key1).get(key2) - 1);
                }
            }
            return count;
        }
    

Log in to reply
 

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