Group multiple occurrences of array elements ordered by first occurrence in C++

In this tutorial, we are going to learn how to group multiple occurrences of array elements in the order of the first occurrence of the elements in C++.

Naive Solution:

Let us assume that our array is A and its size is n. For storing the multiple occurrences of elements in groups we should maintain another array B. At first, we should iterate through the elements of the array A. If we find an element occurring for the first time then we should find all the multiple occurrences of it and store them in the array B in the form of a group. While iterating if we find an element that is not occurring for the first time we should ignore it.

Implementation:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,i,j,k;
    cout<<"Enter the size of the array"<<endl;
    cin>>n;
    int A[n],B[n];
    bool visit[n];
    cout<<"Enter the elements of the array"<<endl;
    for(i = 0;i < n;i++){
        cin>>A[i];
    }
    j=0;
    for(i = 0;i < n;i++){
        if(visit[i] == false){
            for(k = i;k < n;k++){
                if(A[k] == A[i]){
                    B[j] = A[i];
                    j++;
                    visit[k] = true;
                }
            }
        }
    }
    cout<<"Array after grouping"<<endl;
    for(i = 0;i < n;i++){
        cout<<B[i]<<' ';
    }
    cout<<endl;
}

Output:

Enter the size of the array
8
Enter the elements of the array
1 5 3 2 2 1 6 5
Array after grouping
1 1 5 5 3 2 2 6

In the above code, we used a visited array to find out the first occurrence of an element. Initially, all the values of the visited array are false. While iterating if we are at the i-th position of the array A, the boolean value at the i-th position in the visited array will indicate whether it is the first occurrence of the element or not. If the value in the visited array is false then we can say that it is the first occurrence of an element. If we find an element occurring for the first time we should mark it as visited and we should also find all the multiple occurrences of that element and mark them as visited. So while iterating, if the boolean value in the visited array is true we can say that it is not the first occurrence of the element.

Time Complexity: O(n*n)

Optimal Solution:

We can use a hash table to store all the distinct elements and their frequencies. To store the order in which the elements have occurred we can maintain a vector. While iterating through the elements of the array, at first we should increment the frequency of the element in the hash table. After incrementing the frequency, if the frequency of the element is 1 we should add that element at the end of the vector as it is the first occurrence of the element. After iterating the array the order of occurrence of the elements will be stored in the vector and their frequencies will be stored in the hash table. Finally, we should iterate the vector to make groups in the order of occurrence using the frequency of the elements in the hash table.

Implementation

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,i,j,k;
    cout<<"Enter the size of the array"<<endl;
    cin>>n;
    int a[n];
    cout<<"Enter the elements of the array"<<endl;
    for(i = 0;i < n;i++){
        cin>>a[i];
    }
    unordered_map<int,int> m;
    vector<int> v;
    //Counting the frequency of all elements
    for(i = 0;i < n;i++){
        m[a[i]]++;
        if(m[a[i]]==1){
            v.push_back(a[i]);
        }
    }
    j=0;
    for(i = 0;i < v.size();i++){
        for(k = 0;k < m[v[i]];k++){
            a[j] = v[i];
            j++;
        }
    }
    cout<<"Array after grouping"<<endl;
    for(i = 0;i < n;i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
    
}

Output:

Enter the size of the array
7
Enter the elements of the array
2 8 8 4 2 5 4
Array after grouping
2 2 8 8 4 4 5

An unordered_map in C++ works like a hash table. On average all the operations such as insertion, searching, etc take O(1) time.

Time Complexity: O(n)

Also read: Check if an unordered map contains a key in C++

We hope that you have got a clear idea on this topic.