Question link

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Solution is done using customized BST where count stores the total number of elements lesser than current element found from left to right.

class Solution:
    def countSmaller(self, nums):
        class Node:
            def __init__(self, val):
                self.val = val
                self.left = None
                self.right = None
                self.count = 0

        def bst_insert(root, val, result, count):
            if not root:
                root = Node(val)
                root.left = None
                root.right = None
                return root
            if val > root.val:
                root.right = bst_insert(root.right, val, result, root.count + 1 + count)
                root.count += 1
                root.left = bst_insert(root.left, val, result, count)
            return root

        root = None
        result = []
        for num in nums[::-1]:
            if not root:
                root = Node(num)
                bst_insert(root, num, result, 0)
        return result[::-1]
  • \$\begingroup\$ What is a "BST"? \$\endgroup\$ – ben rudgers Dec 17 '17 at 13:55
  • \$\begingroup\$ @benrudgers Binary Search Tree. \$\endgroup\$ – Mast Dec 17 '17 at 21:09

The first advice is to remove the class. In python you should use classes when it makes sense to do so, but you don't need to.

Next, your bst_insert has redundant code. root.left = None and root.right = None are already done in your constructor, so you don't need to duplicate them.

The last piece of advice is to use reversed(nums) instead of num[::-1] as the former does not make a copy, which should be faster and use less memory.

Other than that this looks pretty good.

  • \$\begingroup\$ If i remove class then i will get compilation error. Can you modify this ideone.com/9dHWDS and let me know what you mean? \$\endgroup\$ – noman pouigt Dec 17 '17 at 9:06
  • \$\begingroup\$ ideone.com/ZUhsEK \$\endgroup\$ – Oscar Smith Dec 17 '17 at 16:21
  • 2
    \$\begingroup\$ That class is mandatory in leetcode. \$\endgroup\$ – noman pouigt Dec 17 '17 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.