Two Sum IV


  • 0

    Click here to see the full article post


  • 0
    A

    Approach #2 : Space complexity should be O(n). The size of the set+queue can grow upto n in the worst case.


  • 0
    Z

    You didn't use the info Binary Search Tree at all.


  • 0

    @zestypanda I've updated the article. Thanks for the valuable feedback.


  • 0

    @aayushgarg You're right. Thanks for pointing out.


  • 0
    S

    @vinod23 whats your take on converting the BST to doubly linked list and then find the two sum.


  • 0
    K
    This post is deleted!

  • 0
    P

    @kool This cannot be done in O(n) time and O(logN) space. What if height of my BST is N?


  • 0
    D

    Can be good, if the desired optimization (time vs space) was put on challenge description, because a in-place search on this tree can be made at time O(N * log(N)) and space O(1).


  • 0
    A

    @vinod32 My first solution has better bounds than the listed ones. https://leetcode.com/submissions/detail/125833106/ It's similar to approach #3, but only uses O(Depth) space which is log2(N) when the tree is balanced. You do not need to put all tree elements in the list. Just traverse the tree itself.


  • 0
    T

    @Ark-kun 404 Page Not Found. What happened?


  • 1
      def __findTargetDetail(self, root, k, seen):
        if root is None:
          return False
    
        complement = k - root.val
        if complement in seen:
          return True
        else:
          seen.add(root.val)
    
        return self.__findTargetDetail(root.left, k, seen) or self.__findTargetDetail(root.right, k, seen)
    
      # O(n) time, O(n) space
      def findTarget(self, root, k):
        seen = set()
        return self.__findTargetDetail(root, k, seen)
    

  • 1
      def __binarySearch(self, root, k):
        if root is None:
          return
    
        if root.val == k:
          return root
        elif root.val > k:
          return self.__binarySearch(root.left, k)
        else:
          return self.__binarySearch(root.right, k)
    
      def __findTargetBST(self, node, root, k):
        if node is None:
          return False
    
        complement = k - node.val
        comp_node = self.__binarySearch(root, complement)
        if comp_node is not None and node is not comp_node:
          return True
    
        return self.__findTargetBST(node.left, root, k) or self.__findTargetBST(node.right, root, k)
    
      # O(nlogn) time, O(h) space
      def findTarget(self, root, k):
        return self.__findTargetBST(root, root, k)
    

  • 1
      # O(n) time, O(n) space, use BFS
      def findTarget(self, root, k):
        if root is None:
          return False
    
        s = set()
        q = Queue.Queue()
        q.put(root)
        while not q.empty():
          node = q.get()
          complement = k - node.val
          if complement in s:
            return True
          else:
            s.add(node.val)
          if node.left:
            q.put(node.left)
          if node.right:
            q.put(node.right)
        return False
    

  • 0
    E

    /**

    • Definition for a binary tree node.

    • struct TreeNode {

    • int val;
      
    • TreeNode *left;
      
    • TreeNode *right;
      
    • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      
    • };
      /
      class Solution {
      public:
      bool findTarget(TreeNode
      root, int k) {
      if (root == NULL) {
      return false;
      }
      vector<int> v;
      inorder(root, v);

       int low = 0; 
       int high = v.size() - 1;
       while (low < high) {
           if (v[low] + v[high] == k) {
               return true;
           } else if (v[low] + v[high] < k) {
               low++;
           } else {
               high--;
           }
       }
       
       return false;
      

      }

    private:
    void inorder(TreeNode* root, vector<int>& v) {
    if (root != NULL) {
    inorder(root->left, v);
    v.push_back(root->val);
    inorder(root->right, v);
    }
    }
    };


  • 0
    E

    @RF Could you tell me how you reply the code in a readable format?


  • 0

  • 0
    Y
    public boolean findTarget(TreeNode root, int k) {
        
        java.util.Map<Integer, Object> m = new java.util.HashMap<>();
        flat(root, m);
        
        for (java.util.Map.Entry<Integer, Object> e : m.entrySet()) {
            int complement = k - e.getKey();
            if (complement != e.getKey()  // avoid like 6 - 3 = 3 issue;
                && m.containsKey(complement)) {
                return  true;
            }
        }
            
        return false;
       
    } 
    
    /**
    * recursively get values from the tree and put into map.
    */
    public void flat(TreeNode node, java.util.Map<Integer,Object> m) {
        m.put(node.val, null);
        if(node.left != null) flat(node.left, m);
        if(node.right != null) flat(node.right, m);
    }
    

    }


  • 0

    You can also achieve O(h) space if you use a BST Iterator for the min and max node of the tree. Runtime will still be O(n)


Log in to reply
 

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