Group elements of an array based on their first occurrence

Problem

Given an unsorted array, the task is to group multiple occurrences of individual elements. The grouping should happen in a way that the order of first occurrences of all elements is maintained.

Approach

We can use hashmaps in order to solve the problem. First, we store the frequency of each element in a hash map. We now traverse the array and keep the value of this element in a hashmap as -1 once we explore it.

If we see that the value of some element is not -1, we traverse another loop count number of times, where count is the frequency of this element and keeps pushing the values in the answer.

C++ Programming

#include<bits/stdc++.h>
using namespace std;
class Solution{
 int arr[9] = {5, 4, 5, 5, 3, 1, 2, 2, 4};
 int n = sizeof(arr) / sizeof(arr[0]);
 public:
 void solve(){
     unordered_map<int,int>mp;  //map to store frequencies
     for(int i=0;i<n; i++){
         mp[arr[i]]++;
     }
     vector<int>ans;
     for(int i=0; i<n; i++){
         if(mp[arr[i]]!=-1){
             for(int j=0;j<mp[arr[i]];j++)
             {   
                 //another loop runs till count of elements
                 ans.push_back(arr[i]);
             }
             mp[arr[i]]=-1;  //explored the element
         }
     }
     for(auto itr:ans) cout<<itr<<" ";
 }
};
int main(){
   Solution s;
   s.solve();
}

Output

5 5 5 4 4 3 1 2 2

Python Programming

def solve(arr):
   mp = {}


   for i in range(0, len(arr)):
       mp[arr[i]] = mp.get(arr[i], 0) + 1
      
   for i in range(0, len(arr)):
      
       count = mp.get(arr[i]) 
       if count != -1:
          
           for j in range(0, count):
               print(arr[i], end = " ")
           mp[arr[i]]=-1

arr = [5, 4, 5, 5, 3, 1, 2, 2, 4]
solve(arr)

Output

5 5 5 4 4 3 1 2 2

Java Programming

import java.util.HashMap;

class Main
{
   static void solve(int arr[])
   {
      
       HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();

       for (int i=0; i<arr.length; i++)
       {
       Integer prevCount = mp.get(arr[i]);
       if (prevCount == null)
               prevCount = 0;
          
  
       mp.put(arr[i], prevCount + 1);
       }

  
       for (int i=0; i<arr.length; i++)
       {
          
           Integer count = mp.get(arr[i]);
          if (count != null)
           {

               for (int j=0; j<count; j++)
               System.out.print(arr[i] + " ");
              
               mp.remove(arr[i]);
           }
       }
   }
   public static void main (String[] args)
   {
       int arr[] = {5, 4, 5, 5, 3, 1, 2, 2, 4};
       solve(arr);
   }
}

Output

5 5 5 4 4 3 1 2 2

People are also reading:

• Print a given matrix in spiral form
• Construction of an Expression Tree
• Maximum of all Subarrays of size K
• Print a two-dimensional view of a Binary Tree
• Program to Rotate an Array
• Count Inversions
• Merge Two Sorted Arrays in-place
• Sort elements by their frequency and index
• The Stock Span Problem
• Majority Element