This is a LeetCode.com problem. https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/
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].
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
Following is my solution which is accepted. But I noticed my run time is lot higher than many other submissions. I am curious to know if there is a better algorithm to this problem or is it something in the implementation that I can improve? How pythonic is my code? Do you see issues with any logic that could be done in a better way (both performance and code beauty wise)
Algorithm: I start traversing the input list from the end. I take each element and insert it into a BST. While inserting I also track for each node in the BST, how many nodes are left of it (the size of left subtree) which denotes elements that are strictly smaller than current node. I also compute a position variable that starts at zero at root and gets incremented by X, each time a node is visited with value less than the given node where X is the count of its left subtree size plus one. If the number is equal, I only increment it by the node's left subtree count.
class bst_node(object): def __init__(self, val): self.val = val self.left = None self.right = None self.left_count = 0 # less than # Name of this class is given by LeetCode, not my choice. class Solution(object): def add_node(self, bst_pointer, new_node, position): if bst_pointer == None: return position, new_node if new_node.val < bst_pointer.val: bst_pointer.left_count += 1 position, bst_pointer.left = self.add_node(bst_pointer.left, new_node, position) else: if new_node.val > bst_pointer.val: position += 1 position += bst_pointer.left_count position, bst_pointer.right = self.add_node(bst_pointer.right, new_node, position) return position, bst_pointer # This method signature is also given by Leetcode. def countSmaller(self, nums): """ :type nums: List[int] :rtype: List[int] """ res =  bst = None for n in nums[::-1]: smaller_after, bst = self.add_node(bst, bst_node(n), 0) res.append(smaller_after) return res[::-1] # Few test cases ... print(Solution().countSmaller()) print(Solution().countSmaller([5, 2, 6, 1]))