Multi tool use

Count greater elements to the right of self

This question below given is driving me nuts.If anyone can help, please.

"Given an array Num of 'n' elements return an array A of length 'n' in which A[i] contains number of elements greater than Num[i] to its right in the initial array"

I saw an SO answer here but its contains solution of O(n^2). I need a solution of O(nlogn).

I have solution for "Count smaller elements to left of self". But modifying it didn't give me the required solution(refer for code below).

Any help is appreciated:)

class BinarySearchTreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.count = 1
self.leftTreeSize = 0

class BinarySearchTree(object):
def __init__(self):
self.root = None

def insert(self, val, root):
if not root:
self.root = BinarySearchTreeNode(val)
return 0

if val == root.val:
root.count += 1
return root.leftTreeSize

if val < root.val:
root.leftTreeSize += 1

if not root.left:
root.left = BinarySearchTreeNode(val)
return 0
return self.insert(val, root.left)

if not root.right:
root.right = BinarySearchTreeNode(val)
return root.count + root.leftTreeSize

return root.count + root.leftTreeSize + self.insert(val, root.right)

class Solution(object):
def countSmaller(self, nums):

tree = BinarySearchTree()
return [
tree.insert(nums[i], tree.root)
for i in range(len(nums) - 1, -1, -1)
][::-1]

print(Solution().countSmaller(nums = [1, 4, 2, 7]))


Example:

Given array [10, 7, 2, 6, 5]

then smaller to right count array is [4, 3, 0, 1, 0]

greater to left count array is [0, 1, 2, 2, 3]

Hope this helps...

2 Answers
2

Well I don't know if this is the solution you are looking for since I assume that you wanted me to fix your code, but one could approach it this way:

num = [10, 7, 2, 6, 5]

mergeSort(num) or heapSort(num). I don't know if python has those built in, or if you need to implmented yourself. but mergeSort/heapSort it, it has a worst complexity of O(nlog(n).

sortedNum = [2,5,6,7,10]

answer=[ ]

for every number in Num:
binarySearch number in sortedNum and return its position
answer.appened(position)
delete item from sortedNum at position.


The for loop itself has a complexity O(n), and the binarysearch inside the loop has complexity of log(n). So this function has a complexity of O(n log(n)) since the appending and delete takes O(1)

This means that the sorting + the pseudo coded function has a total complexity of O(2nlog(n)) = O(nlog(n)).

Edit: Since I was mistaken and you wanted to count greater elements to the left of self.

No sorting required here!

num = [10,7,2,6,5]

sortedNum = [ ]

answer = [ ]

for every number in Num:
position = binarySearch number in sortedNum to which numbers its inbetween.
insert number into that position into sortedNum
answer.append(len(num)-position)


class Node(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.count = 1
self.rightTreeSize = 0
self.leftTreeSize = 0

class BinarySearchTree(object):
def __init__(self):
self.root = None

def insert(self, val, root):
if not root:
self.root = Node(val)
return 0

if val == root.val:
root.count += 1
return root.rightTreeSize

if val > root.val:
root.rightTreeSize += 1

if not root.right:
root.right = Node(val)
return 0
return self.insert(val, root.right)

if not root.left:
root.left = Node(val)
return root.count + root.rightTreeSize

return root.count + root.rightTreeSize + self.insert(val, root.left)


class BinarySearchTree1(object):
def __init__(self):
self.root = None

def insert(self, val, root):
if not root:
self.root = Node(val)
return 0

if val == root.val:
root.count += 1
return root.leftTreeSize

if val < root.val:
root.leftTreeSize += 1

if not root.left:
root.left = Node(val)
return 0
return self.insert(val, root.left)

if not root.right:
root.right = Node(val)
return root.count + root.leftTreeSize

return root.count + root.leftTreeSize + self.insert(val, root.right)



class Solution(object):
def countGreater(self):
nums = [10, 7, 2, 6, 5]
tree = BinarySearchTree()
print([tree.insert(nums[i], tree.root) for i in range(0, len(nums))])

def countSmaller(self):
nums = [10, 7, 2, 6, 5]
tree1 = BinarySearchTree1()
print([tree1.insert(nums[i], tree1.root) for i in range(len(nums) - 1, -1, -1)][::-1])


Solution().countSmaller()
Solution().countGreater()


Sorry about the indentation issues couldn't adjust all the lines in markdown editor.

The above code returns "Count of smaller elements to right of self" and "Count of greater elements to left of self"

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.