Python O(nlogn) solution using binary search tree


  • 0
    Z
    class Tree(object):
            
        def __init__(self, val):
            self.val = val
            self.size = 1
            self.left = None
            self.right = None
            
        def insert(self, val):
            self.size += 1
            if val < self.val:
                if self.left:
                    self.left.insert(val)
                else:
                    self.left = Tree(val)
            else:
                if self.right:
                    self.right.insert(val)
                else:
                    self.right = Tree(val)
            
        def search(self, val, index=0):
            if val == self.val:
                left_child_size = self.left.size if self.left else 0
                return index + left_child_size
            elif val < self.val and self.left:
                return self.left.search(val, index)
            elif val > self.val and self.right:
                left_size = self.left.size if self.left else 0
                return self.right.search(val, index + left_size + 1)
            else:
                return -1
    
    
    class Solution(object):
        
        def countSmaller(self, nums):
            if not nums:
                return []
            nums.reverse()
            tree = Tree(nums[0])
            smallers = [0]
            for num in nums[1:]:
                tree.insert(num)
                smallers.append(tree.search(num))
            smallers.reverse()
            return smallers

Log in to reply
 

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