Frequency of each element in an unsorted array

Given an unsorted array. The task is to calculate the cumulative frequency of each element of the array using count array.

Examples:

Input : arr[] = [1, 2, 2, 1, 3, 4]
Output :1->2
        2->4
        3->5
        4->6

Input : arr[] = [1, 1, 1, 2, 2, 2]
Output :1->3
        2->6

simple solution is to use two nested loops, the outer loops picks an element from left to right that are not visited. The inner loop counts its occurrences and mark occurrences as visited. Time complexity of this solution is O(n*n) and auxiliary space required is O(n).

better solution is to use sorting. We sort the array so that same elements come together. After sorting, we linearly traverse elements and count their frequencies.

An efficient solution is to use hashing. We use a hash map that uses value as key and frequency as value. We traverse the array and insert all elements and their frequencies. Finally, we traverse the hash map and print key value pairs in it.

// CPP program to count frequencies of
// elements in an unsorted array.
#include <bits/stdc++.h>
using namespace std;
void countFreq(int a[], int n)
{
    // Insert elements and their
    // frequencies in hash map.
    unordered_map<int, int> hm;
    for (int i=0; i<n; i++)
        hm[a[i]]++;
    // Print contents of hash map
    for (auto x : hm)
    cout << "Frequency of " << x.first
        << " is " << x.second << endl;
}
// Driver program
int main()
{
    int a[] = {1, 3, 2, 4, 2, 1};
    int n = sizeof(a)/sizeof(a[0]);
    countFreq(a, n);
    return 0;
}

Output:

Frequency of 4 is 1
Frequency of 2 is 2
Frequency of 3 is 1
Frequency of 1 is 2

Time complexity of the solution is O(n).

What if we need frequencies of elements according to the order of first occurrence?
For example, in array [2, 4, 1, 2, 1, 3, 4], frequency of 2 should be printed first, then of 4, then 1 and finally 3.
We can achieve this in O(n) time only by traversing array twice.
1) Insert elements and their frequencies in hash map.
2) Traverse array again and for every not visited element, print its frequency. For keeping track of visited elements, we use another hash map.

// CPP program to count frequencies of
// elements in an unsorted array.
#include <bits/stdc++.h>
using namespace std;
void countFreq(int a[], int n)
{
    // Insert elements and their
    // frequencies in hash map.
    unordered_map<int, int> hm;
    for (int i=0; i<n; i++)
        hm[a[i]]++;
    unordered_set<int> s;
    for (int i=0; i<n; i++)
    {
       if (s.find(a[i]) == s.end())
       {
           s.insert(a[i]);
           cout << "Frequency of " << a[i]
                << " is " << hm[a[i]] << endl;
       }   
    }
}
// Driver program
int main()
{
    int a[] = {1, 3, 2, 4, 2, 1};
    int n = sizeof(a)/sizeof(a[0]);
    countFreq(a, n);
    return 0;
}

Output :

Frequency of 1 is 2
Frequency of 3 is 1
Frequency of 2 is 2
Frequency of 4 is 1

What if we need frequencies of elements sorted by values?
We can use map instead of unordered_map. map is implemented using self balancing binary search tree and time complexity of search and insert operations is O(Log n).

// Elements are printed in sorted order here
#include <bits/stdc++.h>
using namespace std;
void countFreq(int a[], int n)
{
    // Insert elements and their
    // frequencies in a map
    map<int, int> hm;
    for (int i=0; i<n; i++)
    hm[a[i]]++;
    // Print contents of map.
    for (auto x : hm)
    cout << "Frequency of " << x.first
        << " is " << x.second << endl;
}
// Driver program
int main()
{
    int a[] = {1, 3, 2, 4, 2, 1};
    int n = sizeof(a)/sizeof(a[0]);
    countFreq(a, n);
    return 0;
}

Output:

Frequency of 1 is 2
Frequency of 2 is 2
Frequency of 3 is 1
Frequency of 4 is 1

Time complexity becomes O(k Log k) if we use map where k is number of distinct elements.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar