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
    

Log in to reply
 

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