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].
Example:
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]))
