Beats 100% Java Code


  • 27
    F

    Achieved by only maintaining a list with distinct elements.

    public class TwoSum {
        private List<Integer> list = new ArrayList<Integer>();
        private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        // Add the number to an internal data structure.
    	public void add(int number) {
    	    if (map.containsKey(number)) map.put(number, map.get(number) + 1);
    	    else {
    	        map.put(number, 1);
    	        list.add(number);
    	    }
    	}
    
        // Find if there exists any pair of numbers which sum is equal to the value.
    	public boolean find(int value) {
    	    for (int i = 0; i < list.size(); i++){
    	        int num1 = list.get(i), num2 = value - num1;
    	        if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) return true;
    	    }
    	    return false;
    	}
    }

  • 0
    Y

    hi @FreeLikeWind, I found that using a count map alone is twice as slow. Do you have any idea why?


  • 0
    F

    Could you show me the code?


  • 0
    M

    Same here... why?
    Each time when find() is called, he iterates through the list with distinct elements, while I iterate through the keySet() of the hash map (I guess you are same here...)


  • -1
    M

  • 1

    Same question, why we use a list here?


  • 4
    S

    This is very interesting, using approach utilizing Map.Entry is good, such as https://leetcode.com/discuss/19515/my-solutions-java-and-python-time-for-add-time-for-find-space. but still performed much worse than using a list like this one.

    I think it is due to HashSet<Key> iterator traversing overhead, comparing to good-old positional traversing.

    --- my code using a Map.Entry<>, only beating 50%

    public class TwoSumIII_170 {
    	
    	// inspired by: https://leetcode.com/discuss/19515/my-solutions-java-and-python-time-for-add-time-for-find-space
    	// to use Entry<Key,Val> to optimize, but still no where near the performance
    	// using a List<Key> that contains all distinct values from: 
    	// https://leetcode.com/discuss/76823/beats-100%25-java-code
    	
    	// I suspect that this is due to the performance drag by the Set's iterator 
    	
        Map<Integer, Boolean> num2dupMap = new HashMap<Integer, Boolean>();
    	
        // Add the number to an internal data structure.
        public void add(int number) {
        	
        	// add number to a map, if already exist, set it to true    	
        	num2dupMap.put(number, num2dupMap.containsKey(number));
        }
    
        // Find if there exists any pair of numbers which sum is equal to the value.
        public boolean find(int value) {
        
        	// for each of the number in the map, get the (value - number)
        	// try to find (value - number) in the map
        	// if it exits in the map, 
        	for(Entry<Integer, Boolean> entry: num2dupMap.entrySet()){
        		int num1 = entry.getKey();
        		int num2 = value - num1;
        		if (num1 == num2 && entry.getValue()){
        			// 1. could be number2 = (value - number1) hence to make sure it not only 
        			// 	just found the original number, but a 2nd number of the same value, 
        			// 	we need to && map.get(number2) == true
        			//  then return true
        			return true;
        		} else if (num1 != num2 && num2dupMap.containsKey(num2)){
        			// 2. could be number2 != (value - number1), and if we `enter code here`found it, we 
        			// 	found a winner
        			return true;
        		}
        	}
        	return false;
        }
    }

  • 0
    L

    I think you are right.


  • 0
    S

    Using a LinkedHashMap like this Map<Integer, Boolean> num2dupMap = new java.util.LinkedHashMap<Integer, Boolean>(), leads to faster iteration.

    See here for details: http://stackoverflow.com/questions/3870064/performance-considerations-for-keyset-and-entryset-of-map


  • 5
    L

    This code shows that ArrayList is far more fast than HashMap's iterator 233


  • 1
    B

    This solution should be upvoted, because actually this runs, the others are TLE. This List trick is very nice! Thanks for sharing!


  • 1
    J

    @yanggao I guess maybe extent size of map cause rehashing


  • 0

    I am really amazed. Iterating List turns out to be much faster than iterating on HashMap.keySet().


  • 0

    @magicshine

    HashMap + HashSet combo turns out to be slow, so using List is preferable.

    public class TwoSum {
        private Set<Integer> set = new HashSet<Integer>();
        private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
    	public void add(int number) {
    	        map.put(number, map.getOrDefault(number, 0) + 1);
    	        set.add(number);
    	}
    	public boolean find(int value) {
    	    for (int i : set)
    	        if ((i == value - i && map.get(i) > 1) || (i != value - i && map.containsKey(value - i))) 
    	            return true;
    	    return false;
    	}
    }

  • 0
    E

    There's nothing surprising that iterating a count map is slower than iterating a list, if you take a look at the source code of Java hashmap, or simply take a look at Java doc:
    https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

    Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).
    

  • 0

    using list is really fast!
    here is my code without using List

    public class TwoSum {
        Map<Integer, Integer> map = new HashMap<>();
        /** Add the number to an internal data structure.. */
        public void add(int number) {
            map.put(number, map.getOrDefault(number,0)+1);
        }
        
        /** Find if there exists any pair of numbers which sum is equal to the value. */
        public boolean find(int value) { 
            for(Integer k : map.keySet()){
                int t = value - k;
                if((t == k && map.get(k) > 1) || (t != k && map.containsKey(t))) return true;
            }
            return false;
        }
    

Log in to reply
 

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