Suppose I have an input array where all objects are non-equivalent - e.g. [13,2,36]. I want the output array to be [1,0,2], since 13 is greater than 2 so "1", 2 is greater than no element so "0", 36 is greater than both 13 and 2 so "2". How do I get the output array with efficiency better than O(n2)? Edit 1 : I also want to print the output in same ordering. Give a c/c++ code if possible.

# Best How To :

Seems like a dynamic programming. May be this can help Here is an O(n) algorithm

**1.Declare an array of say max size say 1000001;**

**2.Traverse through all the elements and make arr[input[n]]=1 where input[n] is the element**

**3.Traverse through the arr and add with the previous index(To keep record of arr[i] is greater than how many elements) like this**

```
arr[i]+=arr[i-1]
```

Example: if input[]={12,3,36}

After step 2

arr[12]=1,arr[3]=1,arr[36]=1;

After step 3

arr[3]=1,arr[4]=arr[3]+arr[4]=1(arr[4]=0,arr[3]=1),

arr[11]=arr[10]=arr[9]=arr[8]=arr[7]arr[6]=arr[5]=arr[4]=1

arr[12]=arr[11]+arr[12]=2(arr[11]=1,arr[12]=1)

arr[36]=arr[35]+arr[36]=3(because arr[13],arr[14],...arr[35]=2 and arr[36]=1)

**4.Traverse through the input array an print **`arr[input[i]]-1`

where i is the index.

So arr[3]=1,arr[12]=2,arr[36]=3;

If you print arr[input[i]] then output will be {2,1,3} so we need to subtract 1 from each element then the output becomes {1,0,2} which is your desired output.

//pseude code

```
int arr[1000001];
int input[size];//size is the size of the input array
for(i=0;i<size;i++)
input[i]=take input;//take input
arr[input[i]]=1;//setting the index of input[i]=1;
for(i=1;i<1000001;i++)
arr[i]+=arr[i-1];
for(i=0;i<size;i++)
print arr[input[i]]-1;//since arr[i] was initialized with 1 but you want the input as 0 for first element(so subtracting 1 from each element)
```

To understand the algorithm better,take paper and pen and do the dry run.It will help to understand better.

Hope it helps Happy Coding!!