Leetcode Count of Smaller Numbers After Self solution

Question

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
 result.append(count)
 return root
 if val > root.val:
 root.right = bst_insert(root.right, val, result, root.count + 1 + count)
 else:
 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)
 result.append(0)
 else:
 bst_insert(root, num, result, 0)
 return result[::-1]

• ben rudgers: What is a "BST"?
• Mast: @benrudgers Binary Search Tree.

Answer 1

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.

• noman pouigt: If i remove class then i will get compilation error. Can you modify this ideone.com/9dHWDS and let me know what you mean?
• Oscar Smith: ideone.com/ZUhsEK
• noman pouigt: That class is mandatory in leetcode.