JSolved: Surpasser Count of each element in an array

JSolved: Surpasser Count of each element in an array

Given an array of distinct integers, for each element of the array count the number of elements to the right that are greater than that element.

A surpasser of an element of an array is a greater element to its right, therefore x[j] is a surpasser of x[i] if i < j and x[i] < x[j].

Example:

input = [6, 5, 4, 7, 2, 8, 0]

output= [2, 2, 2, 1, 1, 0, 0]

Approach 1:

Simplest approach to iterate every time throught the array and find out greater element to it's right. This approach would require O(n^2) complexity and no space complexity.

Approach 2:

We can use O(n)  extra space and solve this efficiently. Priority queue can be used here to store the element in sorted order so that we can check the number of greater element in faster manner. So the complexity will be similar to the time required to push element to priority queue and removing from the same to check for greater element.

Steps:

  
Start from rear end of array, pick one element each time
  
  
Check if queue head is greater than current element 
  
if yes means all the element in queue are greater than current element.
  
  
Save the size of queue as output for specific index of input array
  
  
if no then remove element from queue and store it to stack for temporaty storage.
  
Go to step 1 again

Read full article from JSolved: Surpasser Count of each element in an array