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
A 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).
A 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 growthoriented 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