Java solution O(n) add, O(1) find and O(n) space


  • 3
    R
    public class TwoSum {
        
        Map<Integer, Integer> numToCountMap = new HashMap<>();
        Set<Integer> sums = new HashSet<>();
    
    	public void add(int number) {
    	    for (Integer ele : numToCountMap.keySet()){
    	        sums.add(number + ele);
    	    }
    	    Integer counts = numToCountMap.get(number);
    	    counts = (counts == null) ? 1 : counts+1;
    	    numToCountMap.put(number, counts);
    	}
    
    	public boolean find(int value) {
    	    return sums.contains(value);
    	    
    	}
    }
    

    but I do not understand why OJ gives me a "Time Limit Exceeded". Any help will be greatly appreciated.


  • 1
    R

    later on, I did a O(1) add, O(n) find with O(n) space, the system said it is OK. just let you know

    public class TwoSum {

    Map<Integer, Integer> numToCountMap = new HashMap<>();
    
    public void add(int number) {
        Integer counts = numToCountMap.get(number);
        counts = (counts == null) ? 1 : counts+1;
        numToCountMap.put(number, counts);
    }
    
    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry: numToCountMap.entrySet()) {
            int key = entry.getKey();
            int second = value - key;
            int counts = entry.getValue();
            if ((second == key && counts > 1 )|| (second != key) && numToCountMap.containsKey(second)) {
                return true;
            }
        }
        return false;
    }
    

    }


  • 1
    M

    I think OJ has one (or more?) test case that "add()" a bunch of number but does not try to "find()". I also write an O(n)-time add() and O(1)-time find(). The code is like this

    public:
    void add(int number) {
        
        for(const auto& num:numSet) 
            sumSet.insert(num+number);
        numSet.insert(number);          
    }
    
    bool find(int value) {
        return sumSet.find(value)!=sumSet.end();   
    }
    private:
        unordered_set<int> numSet, sumSet;
    

    To see the failed case just copy and paste.


  • 0
    L

    Thanks for sharing. Btw, O(n) add and O(1) find is not exactly O(n) space, but could be O(n^2) due to the sums set.


  • 0
    L
    This post is deleted!

  • 0
    B

    I want to ask, why is O(n) space?


Log in to reply
 

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