Find frequency of each element in an Array in C++

In this tutorial, we are going to see how to frequency of each element in an Unsorted array in C++.

There are many ways to solve this problem, in this tutorial we will see the brute force approach and the most optimized approach that is hashing.

The arrangement of the elements in the array will be random.

Example:

Input -> {3,4,3,5,5,1,1,1,2,2,4}

//Elements along with their frequency is displayed
Output:
3 -> 2 times
4 -> 2 times
5 -> 2 times
1 -> 3 times
2 -> 2 times

C++ program to find the frequency of elements in an Array

BRUTE FORCE

In this we will use the classical approach to every problem, that is to solve using nested loops.
For this problem, we will use two loops one for picking an element and another for counting its frequency, this is a simple approach and can easily be implemented.

Time Complexity = O(n²)

Space Complexity = O(n)

Where,
n -> size of the array

USING HASHING

In this technique, we will use a map to store the count of each element. We can use a map if we want to store elements along with their frequency in a sorted fashion else we can use unordered_map.

Let’s see the implementation.

IMPLEMENTATION

#include <bits/stdc++.h>
using namespace std;

//using unordered_map to count and store frequency
void frequencyUnorderedMap(vector<int> a)
{
    unordered_map<int, int> mp;

    //storing elements along with their frequency in unordered_map
    for (int i = 0; i < a.size(); i++)
        mp[a[i]]++;
    unordered_map<int, int>::iterator i;
    cout << "When unordered_map is used\n";

    //displaying elements along with their frequency
    //i->first is element & i->second is its frequnecy
    for (i = mp.begin(); i != mp.end(); i++)
        cout << i->first << " -> " << i->second << " times\n";
    cout << "\n";
}

//using map to count and store frequency
void frequencyMap(vector<int> a)
{
    map<int, int> mp;

    //storing elements along with their frequency in map
    for (int i = 0; i < a.size(); i++)
        mp[a[i]]++;
    map<int, int>::iterator i;
    cout << "When map is used\n";

    //displaying elements along with their frequency
    //i->first is element & i->second is its frequnecy
    for (i = mp.begin(); i != mp.end(); i++)
        cout << i->first << " -> " << i->second << " times\n";
}

int main()
{
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;
    vector<int> a(n);
    cout << "Enter elements of the array: ";
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << "\n";
    frequencyUnorderedMap(a);
    frequencyMap(a);
    return 0;
}

INPUT/OUTPUT

Enter the size of the array: 11
Enter elements of the array: 3 4 3 5 5 1 1 1 2 2 4

When unordered_map is used
2 -> 2 times
1 -> 3 times
5 -> 2 times
3 -> 2 times
4 -> 2 times

When map is used
1 -> 3 times
2 -> 2 times
3 -> 2 times
4 -> 2 times
5 -> 2 times

Time Complexity:
frequencyUnorderedMap = O(n)
frequencyMap = O(nlogn)