Trade off in this problem should be considered


  • 93
    S

    The big data test only have the condition that lots of add and few find. In fact, there has to be one operation's time complexity is O(n) and the other is O(1), no matter add or find. So clearly there's trade off when solve this problem, prefer quick find or quick add.

    If consider more find and less add or we only care time complexity in finding.For example, add operation can be pre-done.

    public class TwoSum {
            Set<Integer> sum;
            Set<Integer> num;
            
            TwoSum(){
                sum = new HashSet<Integer>();
                num = new HashSet<Integer>();
            }
            // Add the number to an internal data structure.
        	public void add(int number) {
        	    if(num.contains(number)){
        	        sum.add(number * 2);
        	    }else{
        	        Iterator<Integer> iter = num.iterator();
        	        while(iter.hasNext()){
        	            sum.add(iter.next() + number);
        	        }
        	        num.add(number);
        	    }
        	}
        
            // Find if there exists any pair of numbers which sum is equal to the value.
        	public boolean find(int value) {
        	    return sum.contains(value);
        	}
        }
    

    On the other side

    public class TwoSum {
        Map<Integer,Integer> hm;
        
        TwoSum(){
            hm = new HashMap<Integer,Integer>();
        }
        // Add the number to an internal data structure.
    	public void add(int number) {
    	    if(hm.containsKey(number)){
    	        hm.put(number,2);
    	    }else{
    	        hm.put(number,1);
    	    }
    	}
    
        // Find if there exists any pair of numbers which sum is equal to the value.
    	public boolean find(int value) {
    	    Iterator<Integer> iter = hm.keySet().iterator();
    	    while(iter.hasNext()){
    	        int num1 = iter.next();
    	        int num2 = value - num1;
    	        if(hm.containsKey(num2)){
    	            if(num1 != num2 || hm.get(num2) == 2){
    	                return true;
    	            }
    	        }
    	    }
    	    return false;
    	}
    }

  • 0
    C

    I basicly use the second method except for manual iteration instead of using an iterator, but TLE here.


  • 7
    W

    Don't forget space trade-off.
    Storing all possible sum may lead to O(n2) space.


  • 0
    B

    Both solution is now TLE.


  • 0
    M

    Change the type of HashMap to LinkedHashMap can boost the traversal. Hence, TLE can be avoided.


  • 2

    I think this part is not necessary:

    if(num.contains(number)){
        	        sum.add(number * 2);
    ...
    

    is that right?


  • 0

    why you are so sure one operation should be O(n)?


  • 4
    T

    @chidong it is a clever optimization if you think of it. The problem is a 2-sum so the only possible new sum that could be added is number*2. You don't have to iterate again through the entire set and add all the sums.


  • 0
    H

    @syftalent In the first algorithm

    The find method is using contains method. Doesn't that mean it takes linear time to search through the list?


  • 0
    C
    public class TwoSum {
        ArrayList<Integer> list = new ArrayList<>();
        // Add the number to an internal data structure.
    	public void add(int number) {
            list.add(number);
    	}
    
        // Find if there exists any pair of numbers which sum is equal to the value.
    	public boolean find(int value) {
            HashSet<Integer> set = new HashSet<>();
            for(Integer num : list){
                if(set.contains(value - num)){
                    return true;
                }
                set.add(num);
            }
            return false;
    	}
    }
    

    As @wei88 pointed storing sum will have O(n^2) complexity. I used the second approach but every find is taking O(n) space which might be not good. Any improvements ?


  • 1

    great observations about the trade-offs.

    A couple points to consider:

    • you can simplify your map and just map to Boolean because you are using an integer but only caring about 2 states, occurring once or more than once.
    • this seems like a bit of cheap trick but when I did this I shaved off 30% of my OJ time. For basically no cost you can keep track of min/max to rule out queries for numbers outside the bounds.
    public class TwoSum 
    {
        Dictionary<int,bool> map = new Dictionary<int,bool>();
        int max = int.MinValue;
        int min = int.MaxValue;
        
        public TwoSum() { }
        
        public void Add(int number) 
        {
            map[number] = map.ContainsKey(number);
            max = Math.Max(max, number);
            min = Math.Min(min, number);
        }
        
        public bool Find(int value) 
        {
            if (value < min + min || value > max + max) return false;
            foreach (int x in map.Keys)
            {
                int y = value - x;
                if (map.ContainsKey(y) && (x != y || map[y] == true)) return true;
            }
            return false;
        }
    }
    

  • 0
    A

    @syftalent I use the first solution but it shows time limit exceed. Then I copy your first solution it is also shown time limit exceed. Did you pass the first one?


  • 1
    P

    The add time for 1st solution is O(n^2)


  • 0
    H

    For using ordered data structure, only need to search (value-s)<s elements.

    class TwoSum {
    private:
    map<int,int> s;
    public:
    /** Initialize your data structure here. */
    TwoSum() {

    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        s[number]++;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for(const auto& v : s){
            int diff=value-v.first;
            if(diff<v.first)
            {
                return false;
            }
            else if(diff==v.first && v.second>1){
                return true;
            }
            else if(diff!=v.first && s.find(diff)!=s.end())
            {
                return true;
            }
        }
        return false;
    }
    

    };


  • 1
    # O(1) add time, O(n) find time, O(n) space
      def __init__(self):
        """
        Initialize your data structure here.
        """
        self.__num_dict = {}
          
    
      def add(self, number):
        """
        Add the number to an internal data structure..
        :type number: int
        :rtype: void
        """
        if number in self.__num_dict:
          self.__num_dict[number] += 1
        else:
          self.__num_dict[number] = 1
          
    
      def find(self, value):
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        :type value: int
        :rtype: bool
        """
        for num in self.__num_dict.keys():
          complement = value - num
          if complement in self.__num_dict:
            # No duplicate element
            if complement != num:
              return True
            # Check if there are two dupliate element can add together to target
            elif self.__num_dict[num] > 1:
              return True
    
        return False
    

  • 1

    Time Limit Exceeded, looks like the big data is more add heavy than find. We should optimize find if in that case.

      # O(n)add time, O(1) find time, O(n^2) space
      def __init__(self):
        """
        Initialize your data structure here.
        """
        self.__nums = set()
        self.__sums = set()
          
    
      def add(self, number):
        """
        Add the number to an internal data structure..
        :type number: int
        :rtype: void
        """
        for num in self.__nums:
          s = num + number
          if s not in self.__sums:
            self.__sums.add(s)
    
        if number not in self.__nums:
          self.__nums.add(number)
    
      def find(self, value):
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        :type value: int
        :rtype: bool
        """
        return True if value in self.__sums else False
    

Log in to reply
 

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