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.

C++

Download   Run Code

Output:

5 5 5 4 4 3 1 2 2

Java

Download   Run Code

Output:

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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
minirop
Guest

I added a vector to avoid having to “std::find + std::erase” the map: https://ideone.com/iEG2b1