How to Find Most Frequent Element in an Array C++

1. Use std::sort Algorithm With Iterative Method to Find Most Frequent Element in an Array
2. Use std::unordered_map Container With std::max_element Function to Find Most Frequent Element in an Array

This article will demonstrate multiple methods about how to find the most frequent element in an array C++.

Use std::sort Algorithm With Iterative Method to Find Most Frequent Element in an Array

The plain solution to find the most frequent element in an array is to traverse the sorted version of the array and keep counts of element frequencies. In this case, we assume that the array is a sequence of integers, and they are stored in a std::vector container.

At first, we need to sort the array of integers using the std::sort algorithm, making one-time traversal sufficient to find the most frequent element. Note that we need several variables during the iteration. Namely, we store the integer from the last iteration to compare to the current element; also, we keep the value of the most frequent integer updated on each cycle of the loop. The algorithm checks if the current element is equal to the previous one and increments the frequency counter when the expression is true. When not true, we check if the current frequency count is greater than the maximum encountered so far, and if so, we store the updated values for the maximum frequency count and the most frequent element.

Then we modify the previous integer variable and reset the current frequency to 1. Once the loop finishes, there’s one more if condition to compare current and maximum frequencies, and then we can identify the result element.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::vector;

int getMostFrequentElement(vector<int> &arr) {
  if (arr.empty()) return -1;

  sort(arr.begin(), arr.end());

  auto last_int = arr.front();
  auto most_freq_int = arr.front();
  int max_freq = 0, current_freq = 0;

  for (const auto &i : arr) {
    if (i == last_int)
      ++current_freq;
    else {
      if (current_freq > max_freq) {
        max_freq = current_freq;
        most_freq_int = last_int;
      }

      last_int = i;
      current_freq = 1;
    }
  }

  if (current_freq > max_freq) {
    max_freq = current_freq;
    most_freq_int = last_int;
  }

  return most_freq_int;
}

int main() {
  vector<int> arr = {1, 2, 3, 4,  5,  6, 7, 8, 9, 10, 2, 3, 4, 5,  6,
                     7, 8, 9, 10, 10, 2, 3, 4, 5, 6,  7, 8, 9, 10, 10};

  int ret = getMostFrequentElement(arr);
  if (ret == -1) {
    perror("getMostFrequentElement");
    exit(EXIT_FAILURE);
  }
  cout << "Most frequent element = " << ret << endl;

  exit(EXIT_SUCCESS);
}

Output:

Most frequent element = 10

Use std::unordered_map Container With std::max_element Function to Find Most Frequent Element in an Array

Alternatively, we can utilize the std::unordered_map class to accumulate frequencies for each element and then call the std::max_element algorithm to identify the element with the biggest value. Note that accumulating frequencies requires a traversal of the whole array and inserting in the map each iteration. In this case, std::max_element method takes three arguments, the first two: the range beginning and ending specifiers. The third argument is the lambda function to compare the elements of the std::unordered_map, which are of type std::pair. Finally, we can return the second item from the pair max_element algorithm returned.

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

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::unordered_map;
using std::vector;

int getMostFrequentElement(vector<int> &arr) {
  if (arr.empty()) return -1;

  unordered_map<int, int> freq_count;

  for (const auto &item : arr) freq_count[item]++;

  auto most_freq_int = std::max_element(
      freq_count.begin(), freq_count.end(),
      [](const auto &x, const auto &y) { return x.second < y.second; });

  return most_freq_int->first;
}

int main() {
  vector<int> arr = {1, 2, 3, 4,  5,  6, 7, 8, 9, 10, 2, 3, 4, 5,  6,
                     7, 8, 9, 10, 10, 2, 3, 4, 5, 6,  7, 8, 9, 10, 10};

  int ret = getMostFrequentElement(arr);
  if (ret == -1) {
    perror("getMostFrequentElement");
    exit(EXIT_FAILURE);
  }
  cout << "Most frequent element = " << ret << endl;

  exit(EXIT_SUCCESS);
}

Output:

Most frequent element = 10