Why a O(n^2) preprocessing time while O(1) for shortest not a good idea?


  • 14
    H

    We can use a hash map to store the shortest distances for any pair of words.


  • -3
    H

    I think the reason is that you should write hashcode and equals for your own class. It's hard to write a right hashcode function without conflicts.


  • 22

    I did the same thing after I got TLE and thought on it for sometime i realized the O(n^2) + O(1) solution is a poor decision any time n (the number of words) > the number of times shortest method is called. Lets take an example say n = 64 and shortest is called 20 times. Now if we look at the approximate total number of operations in our O(n^2) + O(1) solution we would get 64^2 + 20 = 4116. now if you observe others O(n)+O(n) solution their approximate total number of operations would be 64 + (20 * 64) = 1280.

    In short O(n^2) + O(1) solution is only better if shortest is called n times.


  • 5
    V

    But as the questions addressed, shortest is going to be call "many time". In my opinion, calling it less than the number of the words array times, it's not "many time".


  • 1
    Y

    Great idea if shortest() is called a million times.


  • 4

    Agree. Actually this is the first thing I did for this problem! Since the problem clearly states that the shortest distance will be called for many times, so it indicates to sacrifice space for time.
    Consider if number of shortest(,) is called MUCH more than word.size(), then definitely we should registered the distance for each pair (word1, word2), where just to make sure word1 < word2 for uniqueness.

    Another way to comprise both space and time is that we still define the hash map for pairs in the class, but do NOT populate in constructor. Every time a shortest(,) is called, check whether its value already registered before searching in word list. This way won't waste a single computation if calls with the same pairs are made, and won't compute a useless distance of a pair if it is never called.


  • 0

    @mlblount45 For this problem, should consider "called many times" as significantly larger than words.size().


  • 0
    F

    @mlblount45

    Both ideas are correct. It totally depends on how leetcode's test data are set up. I coded the O(n^2) + O(1) first and got a TLE too.Then I know leetcode doesn't like this. So I immediately coded the O(n) + O(n) one as this one is actually much simpler to code.


  • 0
    Y

    @mlblount45 You are absolutely right. But I think the easiest way to put it is that quadric is BAD. If you have implemented something in O(n^2), it is going to bite you. The bottom line is O(nlogn). If you have to implement something in O(n^2), remember to have some safety measures. Otherwise you are out there without pants. O(n^2) is a sweet spot for DoS attack or failure.


  • 1
    A

    Giving TLE - 11/12 Test Cases passed, last one giving TLE

    HashMap<String, Integer> map1;
        public ShortestWordDistanceII(String[] words, boolean b) {
            map1 = new HashMap<>();
            for (int i = 0; i < words.length; i++) {
                for (int j = i + 1; j < words.length; j++) {
                    if (!words[i].equals(words[j])) {
                        String st = "";
                        if (words[i].compareTo(words[j]) < 0)
                            st = words[i] + words[j];
                        else
                            st = words[j] + words[i];
                        if (map1.containsKey(st))
                            map1.put(st, Math.min(map1.get(st), Math.abs(i - j)));
                        else
                            map1.put(st, Math.abs(i - j));
                    }
                }
            }
        }
    
        public int shortest1(String word1, String word2) {
            if (word1.compareTo(word2) < 0)
                return map1.get(word1 + word2);
            else
                return map1.get(word2 + word1);
        }
    

Log in to reply
 

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