Group elements of an array based on their first occurrence

Posted in

Group elements of an array based on their first occurrence

Vinay Khatri
Last updated on June 9, 2022

    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 explored 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 keep 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:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments