Hashing: Given an array, you need to count the frequency if the array elements

Problem Statement:

You are given an array, you need to find the frequency of each distinct element.

Example:

Input:

arr = [1, 2, 1, 2, 3, 4, 3, 3, 5]
Output:

[1, 2] : element 1 is repeated 2 time(s)
[2, 2] : element 2 is repeated 2 time(s)
[3, 3] : element 3 is repeated 3 time(s)
[4, 1] : element 4 is repeated 1 time(s)
[5, 1] : element 5 is repeated 1 time(s)

Solution 1: Hashing approach

Traverse the array, then store the elements as keys and their frequency as values.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> solution(vector<int>& arr) 
{
    
    unordered_map<int, int> mp;      
    vector<vector<int>> ans;         

    for (int num : arr) 
    {
        mp[num]++;
    }

    for (auto &it : mp)
    {
        ans.push_back({it.first, it.second});
    }

    return ans ;
}

int main() 
{
    vector<int> arr = {1, 2, 1, 2, 3, 4, 5, 1, 2, 6, 7};

    vector<vector<int>> ans = solution(arr);

    for (auto &x : ans) {
        cout << x[0] << " " << x[1] << endl;
    }

    return 0;
}

Output

7 1
6 1
5 1
4 1
3 1
2 3
1 3