Explanation of Java TLE and Code to pass using one HashMap. around 90%


  • 3
    C

    So there are mainly two ways to think about this

    • O(n) add, O(1) search (TLE for sure according to leetcode, which I think we should not mind it, it's a trade-off depending on R/W ratio)
    • O(1) add, O(n) search

    Most people take the second approach by recording the <Number, Number Count> using HashMap, in Java. But this leads to TLE. Refer to post:

    https://leetcode.com/discuss/19515/my-solutions-java-and-python-time-for-add-time-for-find-space)

    Some other posts solve this by two things:

    1. Use an extra List to record original numbers
    2. Keep only unique numbers in that list

    For example see posts:

    https://leetcode.com/discuss/73775/my-beats-99-49%-java-submission
    https://leetcode.com/discuss/76823/beats-100%-java-code

    Here we take another approach to solve this. As the first post pointed out, the difference between HashMap and LinkedList is the (random vs linear) memory access pattern. So inspired by that why not using LinkedHashMap? The code can pass beats 85-90%

    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
    public void add(int number) {
        map.put(number, map.getOrDefault(number,0)+1);
    }
    
    public boolean find(int value) {
    
        for (int n1:map.keySet()) {
            int n2 = value - n1;
            if (map.containsKey(n2) && (n1 != n2 || map.get(n1) > 1))
                return true;
        }
        return false;
    }

  • -1
    C

    Line 2: error: cannot find symbol: class LinkedHashMap


  • 0
    C

    add an import to top of the file would solve the problem. I think leetcode excluded some of the utility classes.

    import java.util.LinkedHashMap;


  • 0
    A

    I think that the fact that LinkedHashMap passed tests is just lucky coincidence, because sources show that in JDK6 and JDK7 keySet was inherited from HashMap.
    Hard to say how leetcode should have implemented those tests, but now something is completely broken.

    • the fact that you don't need, actually, to store amount of numbers, but just a flag, if amount is 1 or more than 1

    Actually I've replaced in code similar to yours LinkedHashMap to HashMap and it passed, beating 30% of submissions. Later it didn't passed... Leetcode is broken on that test.


  • 0
    W

    LinkedHashMap does improve the performance a lot.


Log in to reply
 

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