C++: Count Frequencies of Array Elements

Summary: In this programming example, we will learn two different methods to count the frequency of unique elements of an array in C++.

Example:

Input:  {1, 1, 2, 1, 2}

Output: 1 : 3
        2 : 2

Method 1: Using Two Loops

Using two loops, we can match each element of an array with all the elements of the same array. By doing so, we get the number of occurrences of each unique element of the given array.

#include <iostream>
using namespace std;

int main() {
    int n, count;
    
    //enter the size of the array
    cout << "Enter the size of the array: ";
    cin >> n;
    
    //declare input and visited array, both of size 'n'
    int array[n], visited[n];
    
    //take inputs in the array
    cout << "Enter " << n << " numbers in the array: ";
    for(int i=0; i<n; i++){
        cin >> array[i];
    }
    
    //loop through the elements of the array
    for(int i=0; i<n; i++){
        //check if the element has already been counted (visited)
        //if so, then skip the element
        if(visited[i] == 1)
            continue;
         
        //otherwise, check the match with every element of the array
        count = 0;   
        for(int j=0; j<n; j++){
            if(array[i] == array[j]){
                //if the match is found:
                //1. increment the count, and
                //2. mark it visited
                visited[j] = 1;
                count++;
            }
        }
        //output the count
        cout << array[i] << ": " << count << endl;
    }

    return 0;
}

Output:

Enter the size of the array: 5
Enter 5 numbers in the array: 1 1 2 1 2
1 : 3
2 : 2

In this program, we did the following:

1. Ask the user to input the size of the array.
2. Define two arrays (array[n], visited[n]) of the same size.
3. Inside a for loop, ask the user to input elements in the array.
4. After taking input, loop through the array elements.
   1. Inside the loop, check if the particular element (array[i]) has already been counted (i.e. visited[i] == 1).
   2. If so, then skip the element using the continue statement.
   3. Otherwise, using a nested loop and compare the current element (array[i]) with all the elements of the array.
      1. On the successful match, increment the count (count++) and mark the element as counted (visited[i] == 1).
   4. Output the count after the end of the nested loop.
5. End the Program.

The visited array keeps track of the unique element that has already been counted. This prevents the re-counting of the already counted elements.

Because of the nested for loops, this method has the time complexity of O(n²). There is another way using which we can count the frequencies of the elements more efficiently, and that is. by using a map or hashmap.

Method 2: Using Map

In this method, we store each unique element and its count as a key-value pair in a std::map and iterate through the array to update the corresponding count of each element.

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n, count;
    
    //enter the size of the array
    cout << "Enter the size of the array: ";
    cin >> n;
    
    //declare input array of size n
    int array[n];
    
    //take inputs in the array
    cout << "Enter " << n << " numbers in the array: ";
    for(int i=0; i<n; i++){
        cin >> array[i];
    }
    
    //define a map of type <int, int> 
    map<int, int> frequency;
    
    //loop through the elements of the array, and
    //update the frequency of unique elements in the map
    for(int i=0; i<n; i++){
        frequency[array[i]]++;
    }
    
    //output all the frequencies
    for(auto x: frequency){
        cout << x.first << " : " << x.second << endl;
    }

    return 0;
}

Output:

Enter the size of the array: 10
Enter 10 numbers in the array: 1 1 2 1 3 5 1 2 2 5
1 : 4
2 : 3
3 : 1
5 : 2

The type of key-value of map is <int, int>, so for every new element, the value (count) is by default 0.

Since in this method we are using a single ‘for’ loop, its time complexity is O(n), which is better than the first method.

Theses are the two methods using which we can count frequencies of array elements in C++.