Count smaller elements on right side in an array
  • array
  • binarysearchtree
  • binarytree
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (7950)
  • Comments (1)

Suppose you are given an unsorted array. Write a function to count the number of smaller elements on the right of each element.


Could someone please provide a Java code for this solution? - posted 3 years ago @hmhs.hoseini

Posted Answers

We can use a self balancing Binary Search Tree to count the number of smaller elements to the right side of an element in an array. Each node in the tree contains size of its left subtree. The algorithm works as :


  • Iterate through the array from right to left and compare the key to the root of the tree.
  • If the key is greater than the root, then it will be greater than all the elements in the current left subtree. Insert the key in the right subtree recursively and the count of smaller elements on its right side will be increased by (the size of the current left subtree + \( 1 \)).
  • If the key is less than the root, insert the key in the left subtree recursively and there will be no change in the count of smaller elements on its right side.

Time complexity to insert each element in the Binary Search Tree and count the number of smaller elements on its right side is \( logn+constant \) = \( O(logn) \).
\( \therefore \) Overall time complexity = \( O(nlogn) \).

You need to Sign In to post your solution.