You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low = number of elements lower
than or equal to ar in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
Use BST with one extra frequency field containing number of occurrences-1.
ReplyDeleteStart from right to left, & for each item insert it into BST. If item is already there, increment its frequency.
Whenever an item is found greater than the root while inserting, return 1 + freq of the root node.
#include
struct node
{
int data;
int freq;
struct node *left,*right;
};
struct node* getNode(int data)
{
struct node* temp=(struct node*)malloc(sizeof(struct node));
temp->left=temp->right=NULL;
temp->data=data;
temp->freq=0;
return temp;
}
int insert(struct node**root,int data)
{
if(!*root)
{
*root=getNode(data);
return 0;
}
else if(data<(*root)->data)
return insert(&((*root)->left),data);
else if(data>(*root)->data)
return 1 + (*root)->freq + insert(&((*root)->right),data);
else
{
++((*root)->freq);
return (*root)->freq;
}
}
void cal(int *arr,int size)
{
struct node *root=NULL;
int i,temp[size];
for(i=size-1;i>=0;i--)
{
temp=insert(&root,arr);
}
for(i=0;i<size;++i)
printf("%d ",temp);
}
int main()
{
int arr[]={1,3,2,4,5,4,2},size;
size=sizeof(arr)/sizeof(arr[0]);
cal(arr,size);
return 0;
}