Introduction

Arrays are fundamental data structures in programming, providing a convenient way to store and manipulate collections of elements. One common task when working with arrays is counting the frequency of each element. In this chapter, we will explore various methods to efficiently count the frequencies of array elements in C++.

Problem Statement

Given an array of elements, the goal is to determine the frequency of each unique element in the array. This involves counting how many times each distinct element appears in the array.

Examples:

Example 1:

Input array[] = {5, 5, 5, 1, 1, 4}
Output: 
	5 -> 3
	1 -> 2
	4 -> 1

Example 2:

Input: array[] = {3, 5, 3, 2, 8, 5, 5, 2}
Output:
	3: 2
	5: 3
	2: 2
	8: 1

Approaches

Several methods can be employed to count the frequencies of array elements. We will discuss them all:

1️⃣ Naive Approach | Brute Force Approach:

The most straightforward method involves nested loops to iterate through the array and count occurrences. This approach is simple but can be inefficient for large arrays.

Algorithm:

1. Initialize an empty list or array to store visited elements.
2. Iterate through each element in the array.
3. For each element, check if it has already been counted (i.e., it is in the visited list).
4. If not, count the occurrences of that element using a nested loop.
5. Print or store the element and its frequency.
6. Add the element to the visited list.

Code:

#include <iostream>
#include <vector>

void countFrequenciesBruteForce(const std::vector<int>& arr) {
    std::vector<bool> visited(arr.size(), false);

    for (size_t i = 0; i < arr.size(); ++i) {
        if (visited[i]) continue;

        int count = 1;
        for (size_t j = i + 1; j < arr.size(); ++j) {
            if (arr[i] == arr[j]) {
                visited[j] = true;
                ++count;
            }
        }
        std::cout << arr[i] << ": " << count << std::endl;
    }
}

int main() {
    std::vector<int> arr = {3, 5, 3, 2, 8, 5, 5, 2};
    countFrequenciesBruteForce(arr);
    return 0;
}

#include <iostream>
using namespace std;

void countFrequencies(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int count = 1;
        for (int j = i + 1; j < size; j++) {
            if (arr[i] == arr[j]) {
                count++;
                arr[j] = -1; // Mark the element as visited
            }
        }
        if (arr[i] != -1) {
            cout << "Element " << arr[i] << ": " << count << " times" << endl;
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 2, 1, 3, 4, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    countFrequencies(arr, size);
    return 0;
}

// Output
Element 1: 2 times
Element 2: 2 times
Element 3: 2 times
Element 4: 2 times
Element 5: 1 times

Explanation ->

The brute force method involves nested loops to compare each element with every other element in the array, marking visited elements to avoid redundancy.

Complexity Analysis:

• Time Complexity:O(n^2) - The nested loop results in a quadratic time complexity.
• Space Complexity:O(n) - Extra space is used for the visited array.

This approach is inefficient for large arrays due to its O(n^2) time complexity.

2️⃣ Sorting Approach

This approach involves sorting the array first and then counting the frequencies in a single pass.

Sorting and counting take advantage of the fact that identical elements become adjacent after sorting, making it easier to count frequencies.

Algorithm:

1. Sort the array.
2. Initialize a counter and iterate through the sorted array.
3. If the current element is the same as the previous one, increment the counter.
4. If it is different, store or print the previous element and its frequency, and reset the counter for the new element.
5. Print the last element and its count after the loop ends.

Code:

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

void countFrequencies(int arr[], int size) {
    sort(arr, arr + size);
    for (int i = 0; i < size; i++) {
        int count = 1;
        while (i < size - 1 && arr[i] == arr[i + 1]) {
            count++;
            i++;
        }
        cout << "Element " << arr[i] << ": " << count << " times" << endl;
    }
}

int main() {
    int arr[] = {1, 2, 3, 2, 1, 3, 4, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    countFrequencies(arr, size);
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

void countFrequenciesSorting(std::vector<int>& arr) {
    std::sort(arr.begin(), arr.end());

    int count = 1;
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] == arr[i - 1]) {
            count++;
        } else {
            std::cout << arr[i - 1] << ": " << count << std::endl;
            count = 1;
        }
    }
    // Output the frequency of the last element
    std::cout << arr[arr.size() - 1] << ": " << count << std::endl;
}

int main() {
    std::vector<int> arr = {3, 5, 3, 2, 8, 5, 5, 2};
    countFrequenciesSorting(arr);
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n log n) - Sorting the array takes O(n log n) time, and counting frequencies takes O(n).
• Space Complexity:O(1) - No extra space is required apart from the input array, assuming sorting is done in-place.

This approach is more efficient than the brute-force method for larger arrays due to the reduction in time complexity to O(n log n).

3️⃣ Hashing Approach (Optimal Approach):

Hashing provides an efficient way to store and retrieve frequency counts. We will use an unordered_map to map each element to its frequency.

Algorithm:

1. Initialize an empty hash map.
2. Iterate through the array.
3. For each element, increment its count in the hash map.
4. After traversing the array, print or return the elements and their frequencies from the hash map.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>

void countFrequenciesHashMap(const std::vector<int>& arr) {
    std::unordered_map<int, int> frequencyMap;

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

    for (const auto& pair : frequencyMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}

int main() {
    std::vector<int> arr = {3, 5, 3, 2, 8, 5, 5, 2};
    countFrequenciesHashMap(arr);
    return 0;
}

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

void countFrequencies(int arr[], int size) {
    unordered_map<int, int> freqMap;
    for (int i = 0; i < size; i++) {
        freqMap[arr[i]]++;
    }

    for (const auto& entry : freqMap) {
        cout << "Element " << entry.first << ": " << entry.second << " times" << endl;
    }
}

int main() {
    int arr[] = {1, 2, 3, 2, 1, 3, 4, 5, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    countFrequencies(arr, size);
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n) - The array is traversed once, and each insertion and lookup in the hash map takes O(1) on average.
• Space Complexity:O(n) - The hash map stores the frequencies of each element, requiring additional space proportional to the number of unique elements.
• Using Hashing:O(N) time complexity for iterating through the array once and O(u) space complexity where u is the number of unique elements.

This approach is the most efficient in terms of both time and space, especially for large arrays with many unique elements.

Hashing uses an unordered map to store the count of each element, providing a more  efficient solution with a time complexity of O(N) in average and worst-case scenarios.