Given a sorted Array A(may contain duplicates):Fill array B such that B contains elements from A with increasing frequencies.

Question

Array A has elements in NON decreasing order.Array B must contain elements from A(duplicates not allowed in B) in increasing order of their frequency.If two or more elements have same frequency then array B should contain that
element first which appears first in A.
example:
Array A: 1 1 2 2 2 3 3 4 5
Array B: 4 5 1 3 2 (EXPECTED)

Try to Solve it in as efficient way as you can.

Answer 1

the array A is sorted , so you can use the binary search to get the index of each element in the case of the tie .
this is an implement of this idea , hope this will be helpful.
https://code.sololearn.com/cn5sdrr1S2y5/#cpp

Answer 2

@Mohamed Hamada
what is the complexity of your solution?
also you have used freq[v[i]] .What if v[i](User input) have -ve values?

Answer 3

O(NlogN).
it's ok if v[i] is a -ve ... i'm using the map !
about map (is needed )
http://www.cplusplus.com/reference/map/map/