Count The Frequency Of Each Element Of An Array In C++ Program

Counting the frequency of each element in an array is a common task in programming, useful for various data analysis and manipulation scenarios. Understanding how often each distinct value appears provides valuable insights into the dataset.

In this article, you will learn how to count the frequency of each element within an array using different C++ programming techniques, including brute-force iteration, an auxiliary array, and hash maps.

Problem Statement

Given an array of integers, the goal is to determine how many times each unique integer appears within that array. For instance, if an array contains [1, 2, 2, 3, 1, 4], the output should indicate that 1 appears twice, 2 appears twice, 3 appears once, and 4 appears once. This information is crucial for understanding data distribution, identifying modes, or preparing data for further processing.

Example

Consider the input array: [5, 2, 8, 5, 1, 2, 5]

The expected output showing the frequency of each element would be:

• Element 1: 1 time
• Element 2: 2 times
• Element 5: 3 times
• Element 8: 1 time

 

Background & Knowledge Prerequisites

To effectively follow this article, readers should have a basic understanding of:

• C++ Arrays: How to declare, initialize, and access elements in a static array.
• Loops: for loops for iterating through arrays.
• Conditional Statements: if statements for logic.
• Standard Library Containers (for advanced approaches): Familiarity with std::map or std::unordered_map concepts will be beneficial for efficient solutions.

 

Use Cases or Case Studies

Counting element frequencies has numerous practical applications across different domains:

• Data Analysis: Identifying the most frequent items in a dataset (e.g., popular products in sales data, most common words in text).
• Algorithm Optimization: Used as a preliminary step for algorithms that depend on element distribution, like sorting or finding duplicates.
• Database Queries: Similar to SQL GROUP BY and COUNT operations, but performed in-memory on an array.
• Image Processing: Analyzing the frequency of pixel values in an image histogram.
• Frequency-based Caching: Determining which items are accessed most often to optimize cache eviction policies.

 

Solution Approaches

We will explore three distinct methods to count element frequencies, each with its own advantages and trade-offs in terms of simplicity, efficiency, and memory usage.

Approach 1: Using Nested Loops (Brute Force)

This method involves iterating through the array with an outer loop, and for each element, using an inner loop to count its occurrences in the rest of the array. To avoid re-counting, we can mark elements as visited or use an auxiliary boolean array.

• Summary: Iterates through the array, and for each element, scans the remainder of the array to count its occurrences. Uses a boolean array to track visited elements.

 

// FrequencyCount_NestedLoops
#include <iostream>
#include <vector> // Using std::vector for dynamic array and boolean tracking

int main() {
    // Step 1: Initialize the array
    std::vector<int> arr = {5, 2, 8, 5, 1, 2, 5};
    int n = arr.size();

    // Step 2: Create a boolean vector to keep track of visited elements
    std::vector<bool> visited(n, false);

    std::cout << "Element frequencies using Nested Loops:" << std::endl;

    // Step 3: Iterate through the array
    for (int i = 0; i < n; i++) {
        // If the element has already been visited, skip it
        if (visited[i] == true) {
            continue;
        }

        // Step 4: Initialize count for the current element
        int count = 1;

        // Step 5: Iterate from the next element to count occurrences
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) {
                count++;
                visited[j] = true; // Mark as visited to avoid re-counting
            }
        }
        std::cout << "Element " << arr[i] << ": " << count << " time(s)" << std::endl;
    }

    return 0;
}

Run

• Sample Output:

Element frequencies using Nested Loops:
Element 5: 3 time(s)
Element 2: 2 time(s)
Element 8: 1 time(s)
Element 1: 1 time(s)

 

• Stepwise Explanation:

1. Define the input array arr and its size n.
2. Create a std::vector visited of the same size, initialized to false. This helps in marking elements once their frequency has been counted.
3. Start an outer for loop that iterates from i = 0 to n-1.
4. Inside the outer loop, check if arr[i] has already been visited. If true, skip to the next iteration.
5. If not visited, initialize count = 1 for arr[i].
6. Start an inner for loop from j = i + 1 to n-1.
7. Compare arr[i] with arr[j]. If they are equal, increment count and set visited[j] = true.
8. After the inner loop completes, print arr[i] and its count.

Approach 2: Using an Auxiliary Array (for limited range integers)

This approach is highly efficient when the array elements are non-negative integers within a known, relatively small range (e.g., 0 to 100). We can use an auxiliary array (or frequency array) where the index represents an element from the input array, and the value at that index stores its frequency.

• Summary: Creates an auxiliary array initialized to zeros. Iterates through the input array, using each element's value as an index into the auxiliary array and incrementing the count at that index.

 

// FrequencyCount_AuxiliaryArray
#include <iostream>
#include <vector> // Using std::vector for the frequency array
#include <algorithm> // For std::max_element

int main() {
    // Step 1: Initialize the array
    std::vector<int> arr = {5, 2, 8, 5, 1, 2, 5};
    int n = arr.size();

    // Step 2: Determine the maximum element to size the frequency array
    // This approach assumes non-negative integers.
    int max_element = 0;
    if (n > 0) {
        max_element = *std::max_element(arr.begin(), arr.end());
    }

    // Step 3: Create a frequency array (vector) initialized to zeros
    // Size should be max_element + 1 to accommodate elements from 0 to max_element
    std::vector<int> freq(max_element + 1, 0);

    // Step 4: Iterate through the input array and update frequencies
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }

    std::cout << "Element frequencies using Auxiliary Array:" << std::endl;

    // Step 5: Iterate through the frequency array and print elements with count > 0
    for (int i = 0; i <= max_element; i++) {
        if (freq[i] > 0) {
            std::cout << "Element " << i << ": " << freq[i] << " time(s)" << std::endl;
        }
    }

    return 0;
}

Run

• Sample Output:

Element frequencies using Auxiliary Array:
Element 1: 1 time(s)
Element 2: 2 time(s)
Element 5: 3 time(s)
Element 8: 1 time(s)

 

• Stepwise Explanation:

1. Define the input std::vector arr and its size n.
2. Find the max_element in the array. This is crucial for correctly sizing the frequency array.
3. Create a std::vector freq of size max_element + 1, initialized with all zeros.
4. Iterate through arr. For each element in arr, use its value as an index into the freq array and increment freq[element].
5. Finally, iterate from 0 to max_element through the freq array. If freq[i] is greater than 0, it means i was an element in the original array, and freq[i] is its count. Print i and freq[i].

Approach 3: Using a Hash Map (std::map or std::unordered_map)

Hash maps (like std::map or std::unordered_map in C++) provide a highly flexible and efficient way to store key-value pairs. Here, the array element will be the key, and its frequency will be the value. This approach works for any data type and range of values. std::map stores elements in sorted order of keys, while std::unordered_map offers average O(1) insertion/lookup but no guaranteed order.

• Summary: Iterates through the array and stores each element as a key in a std::map, incrementing its corresponding value (frequency) with each encounter.

 

// FrequencyCount_HashMap
#include <iostream>
#include <vector>
#include <map> // For std::map

int main() {
    // Step 1: Initialize the array
    std::vector<int> arr = {5, 2, 8, 5, 1, 2, 5};

    // Step 2: Create a std::map to store element frequencies
    // Keys will be array elements, values will be their counts
    std::map<int, int> frequencies;

    // Step 3: Iterate through the array and populate the map
    for (int element : arr) {
        frequencies[element]++; // Increments count for existing key, or inserts new key with count 1
    }

    std::cout << "Element frequencies using Hash Map (std::map):" << std::endl;

    // Step 4: Iterate through the map and print key-value pairs
    // std::map iterates in sorted key order
    for (const auto& pair : frequencies) {
        std::cout << "Element " << pair.first << ": " << pair.second << " time(s)" << std::endl;
    }

    return 0;
}

Run

• Sample Output:

Element frequencies using Hash Map (std::map):
Element 1: 1 time(s)
Element 2: 2 time(s)
Element 5: 3 time(s)
Element 8: 1 time(s)

 

• Stepwise Explanation:

1. Define the input std::vector arr.
2. Create an empty std::map frequencies. The first int is for the element (key), and the second int is for its frequency (value).
3. Iterate through arr using a range-based for loop.
4. For each element, use frequencies[element]++. If element is not yet a key in the map, it will be inserted with a default value of 0, and then incremented to 1. If it already exists, its current frequency will be incremented.
5. Finally, iterate through the frequencies map. Each pair in the map will contain an element (pair.first) and its count (pair.second). Print these pairs.

Conclusion

Counting element frequencies in an array is a fundamental task with multiple solutions. The choice of approach depends on the specific constraints and requirements of your problem. Nested loops provide a straightforward, basic method but are less efficient for large arrays. The auxiliary array approach offers excellent performance but is limited to arrays with non-negative integers within a small, known range. For a highly flexible and generally efficient solution across various data types and ranges, hash maps like std::map or std::unordered_map are typically the preferred choice.

Summary

• Problem: Determine the occurrence count for each unique element in an array.
• Nested Loops (Brute Force): Simple to understand, O(n^2) time complexity, suitable for small arrays. Requires marking visited elements to avoid re-counting.
• Auxiliary Array: O(n + max_element) time complexity and O(max_element) space complexity. Highly efficient for non-negative integers within a small, known range.
• Hash Map (std::map/std::unordered_map): O(n log n) average time complexity for std::map (due to sorting) or O(n) average time complexity for std::unordered_map (unordered). O(k) space complexity, where k is the number of unique elements. Most flexible and generally efficient for diverse data types and ranges.
• Each approach provides a valid solution, with performance and applicability varying based on data characteristics and problem constraints.