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]

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.