Count greater elements to the right of self

Question

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...

Haven’t examined your code yet, but if you can solve “count smaller elements to left of self”, then wouldn’t this work? (1) O(N) Create array Num2 = Num in reverse order with negated values. (2) O(NlogN) Create array A2 by counting smaller elements to left of self in Num2. (3) O(N) Create array A by reversing A2. — Tom Zych, Jun 30 '18 at 12:01
Couldn't get what you are trying to say.Make a pseudo code to explain. — Vivek, Jun 30 '18 at 12:21
I couldn't understand your question, could you add an example? — WebOrNative, Jun 30 '18 at 12:34

WebOrNative · Answer 1 · 2018-06-30T15:20:54.470

1

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)

edited Jun 30 '18 at 15:20

answered Jun 30 '18 at 14:43

WebOrNative

113
1
8

This approach is good.But what I asked for is array which gives **"Count of greater elements to left of self"**. Your pseudo code gives count of small elements to right.In others words I need the output [0, 1, 2, 2, 3] as mentioned in above example. – Vivek Jun 30 '18 at 14:56
Your pseudo code is not clear.In th first line you mean to return position of which element???Can you explain it a little bit with the array [10, 7, 2, 6, 5] – Vivek Jun 30 '18 at 16:04
If done binary search for number to which its inbetween then how can two positions be used.If number=7 then it is between 10 and 2.How to get two positions while only one position is used.Or am I missing something? **Clarify me** – Vivek Jun 30 '18 at 16:12
So return position of where the current number should be stored. With the array [10,7,2,6,5] In the first search, you will add 10, since the array sortedNum is empty you just add it to position 0. In the second search, you will ad 7. since the array sortNum has [10]. you will need to insert it inbetween nothing and number 10. In the FOURTH search, you will and 6. since the array sortNum has [2,7,10]. you will need to insert it at position 1, between 2 and 7. The total length of of sortNum is 3. So 3-1 = 2. – WebOrNative Jun 30 '18 at 17:09
When I mean position, if you had lets say sortedNum = [1,1,1,2,3,4,5,5,5,5,6] and want to add 5 and you want to find the position, the position is inserting it at the last occurence of 5, which is 9. Oh btw, you might want to insert it at position +1 into sortedNum instead of position. – WebOrNative Jun 30 '18 at 17:13
I accept your answer but after doing a binary search of the position we need to move other elements so as to fix the new element in position.Won't that turn the algorithm to O(n^2)???So obviously the worst case complexity is O(n^2). Tried with input of range(10000) and it took 5secs of time. – Vivek Jul 01 '18 at 02:51
I have found a solution using BST itself.Its performs operation in O(logn) and for 'n' elements it becomes O(nlogn).See solution below or [here](https://ide.geeksforgeeks.org/CyzgAEErUp) – Vivek Jul 01 '18 at 06:43
@Vivek Well, binaryt search is worst case O(log(n)), and there are (n) elements. So the total time complexity is actually O(n log(n)). I'm glad you solved your own problem though! – WebOrNative Jul 01 '18 at 12:40
After performing binary search other elements should be moved to place the element at that position.This line in your code **"insert number into that position into sortedNum"**.Won't that add to the complexity?If it adds to above won't the total complexity become O(n^2).Correct me if wrong. – Vivek Jul 01 '18 at 15:03
If you know where to insert it, the insertion has a complexity of O(1), because you have already located exactly where it the memory it is. – WebOrNative Jul 01 '18 at 18:34
Take for example sortedNum = [1,2,4,5]. You need to insert 3 at index 2 of the array. You would have found the location but to insert 3 at position 2 you need to move elements 4, 5 to their next positions in a loop.So won't that add to the complexity is my question.That is O(n) [In worst case all elements may have to be moved] – Vivek Jul 01 '18 at 23:41
Sorry for the late answer, yes you are right! However, this could be fixed with a linked list instead of an array I guess – WebOrNative Jul 12 '18 at 22:52
Yes that could be a solution too.But that costs more space :( – Vivek Jul 12 '18 at 23:35

score 0 · Answer 2 · answered Jul 01 '18 at 06:51

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"

Count greater elements to the right of self

2 Answers2