C++ Program to Find the Most Repeated Element

Problem: Write a C++ program to find the most repeated element in the given array. Most repeated element is that element which has occurred most in whole array.

Example:

Input:  {1, 2, 5, 3, 7, 3, 4, 2, 2, 6}
Output: 2

Input:  {1, 5, 8, 7, 7, 5, 3, 5, 5, 9}
Output: 7

There are several ways we can solve this problem. Let’s see two of the approaches with example.

Method 1: Using Sorting [O(nlogn)]

In this approach, we sort the elements of the array in ascending order then count the frequency of the elements.

By sorting, the duplicates element comes together, which makes counting of the frequency of unique elements easier.

Here is the C++ code that finds the most repeated element using the sorting technique:

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {2, 4, 6, 4, 2, 4, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // sort the array
    std::sort(arr, arr + n);
    
    // initialize variables to keep track of current element and its frequency
    int current_element = arr[0];
    int current_count = 1;
    int max_element = arr[0];
    int max_count = 1;
    
    // iterate through the array
    for (int i = 1; i < n; i++) {
        if (arr[i] == current_element) {
            // if the current element is the same as the previous one, increment the count
            current_count++;
        } else {
            // if the current element is different, check if it has a higher frequency than the previous max
            if (current_count > max_count) {
                max_element = current_element;
                max_count = current_count;
            }
            
            // update the current element and its count
            current_element = arr[i];
            current_count = 1;
        }
    }
    // check if the last element is the most frequent
    if (current_count > max_count) {
        max_element = current_element;
    }
    std::cout << "The most repeated element is: " << max_element << std::endl;
    return 0;
}

Output:

The most repeated element is: 4

Time Complexity: O(nlogn)
Space Complexity: O(1)

In this program, after the sorting the array using std::sort() function, we use two pointers to iterate through the array and keep track of the current element and its frequency to find the most frequent element.

This is not the efficient way of finding the most repeated element, as it involves sorting which increases the time complexity to O(nlogn). Let’s see another approach to solve this problem in O(n).

Method 2: Using Map [O(n)]

In this method we use an unordered_map to store the count of each element in the input array.

For this, we iterate through the input array and update its frequency in the unordered map as map[array[i]]++.

Finally, we iterate through the map and keep track of the element with the highest count and output it.

#include <iostream>
#include <algorithm>
#include <unordered_map>

int main() {
    int arr[] = {2, 4, 6, 4, 2, 4, 5, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Create an unordered_map to store the frequency of each element
    std::unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }

    // Initialize variables to keep track of the most frequent element
    int max_element = 0;
    int max_count = 0;

    // Iterate through the map and update the max element and count
    for (const auto& [element, count] : freq) {
        if (count > max_count) {
            max_element = element;
            max_count = count;
        }
    }

    std::cout << "The most repeated element is: " << max_element << std::endl;
    return 0;
}

Output:

The most repeated element is: 4

Time Complexity: O(n)
Space Complexity: O(n)

Because we have used an auxiliary unordered map to store the frequency of elements, the space complexity grows to O(n).

There are other various ways to find the most occurring element in the array. I have only shown you two of them.