Group elements of an array based on their first occurrence

Given an unsorted array of integers containing many duplicates elements, rearrange the given array such that same element appears together and relative order of first occurrence of each element remains unchanged.


For example,

Input:  { 1, 2, 3, 1, 2, 1 }

Output: { 1, 1, 1, 2, 2, 3 }

Input:  { 5, 4, 5, 5, 3, 1, 2, 2, 4 }

Output: { 5, 5, 5, 4, 4, 3, 1, 2, 2 }

The idea is to use hashing to solve this problem. We store frequency of each element present in the input array in a map. Then we traverse the input array and for each element A[i], two cases are possible –

  • If A[i] exists in the map, then this is first occurrence of A[i] in input array. We print element A[i] k times where k is the frequency of A[i] in the input array (stored in map). Finally we delete A[i] from the map so it would not get processed again.
  • If A[i] is not present in the map, then this is repeated occurrence of A[i], and move to the next element.


Download   Run Code


5 5 5 4 4 3 1 2 2


Download   Run Code


5 5 5 4 4 3 1 2 2

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon

Leave a Reply

newest oldest most voted
Notify of

I added a vector to avoid having to “std::find + std::erase” the map: