Problem Statement

Given an array of n integers, find the most frequent element in it i.e., the element that occurs the maximum number of times. If there are multiple elements that appear a maximum number of times, find the smallest of them.

Examples

Example 1:

Input: array = [1, 2, 2, 2, 3, 3]
Output: 2

Explanation: Since the number 2 appears the most (3 times). It is the frequent element.

Example 2:

Input: array = [1, 1, 2, 2, 3]
Output: 1

Explanation: Both 1 and 2 appears twice, however 1 is smaller. So, 1 is the most frequent element.

Example 3:

Input: array = [5, 4, 3, 2, 1]
Output: 1

Explanation: All the elements appear once, however 1 is the smallest among them.

Approaches

1️⃣ Brute Force Approach

Intuition:

A brute-force way to solve this problem will be to use two loops:

• First loop to iterate on the array, selecting an element.
• Second loop to traverse the remaining array to find the occurrences of the selected element in the first loop.

Maintain a visited array to mark the elements to keep track of duplicate elements that were already taken into account.

Approach:

1. Initialize a visited array of boolean type having size n, where n is the size of the array with all elements set to false. Also, declare the following variables :
   1. maxFreq - to store the frequency of the highest occurring element.
   2. maxEle - to store the highest occurring element in the array.
2. In the first loop, start iterating on the elements of the array selecting one element at a time.
3. In the second loop, iterate on the rest portion of the array and count the frequency (number of occurrences) of the selected element. And every time, the same element is found, mark the corresponding index in the visited array as true.
4. If the frequency of the current element is found greater than maxFreq, update maxFreq and maxEle with the new frequency and new element respectively.
5. If the frequency of the current element is the same as maxFreq, store the smaller of maxEle and the current element in maxEle.
6. Before starting the second loop, check if the element is marked as unvisited. Skip the element if it is visited because its frequency has already been taken into consideration.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to get the highest 
    occurring element in array nums */
    int mostFrequentElement(vector<int> &nums) {
        
        // Variable to store the size of array
        int n = nums.size();
        
        // Variable to store maximum frequency
        int maxFreq = 0; 
        
        /* Variable to store element 
        with maximum frequency */
        int maxEle;
        
        // Visited array
        vector<bool> visited(n, false);
        
        // First loop
        for(int i = 0; i < n; i++) {
            // Skip second loop if already visited
            if(visited[i]) continue;
            
            /* Variable to store frequency
            of current element */
            int freq = 0;
            
            // Second loop
            for(int j = i; j < n; j++) {
                if(nums[i] == nums[j]) {
                    freq++;
                    visited[j] = true;
                }
            }
            
            /* Update variables if new element having 
            highest frequency is found */
            if(freq > maxFreq) {
                maxFreq = freq;
                maxEle = nums[i];
            } else if(freq == maxFreq) {
                maxEle = min(maxEle, nums[i]);
            }
        }
        
        // Return the result
        return maxEle;
    }
};

int main() {
    vector<int> nums = {4, 4, 5, 5, 6};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    highest occurring element in array nums */
    int ans = sol.mostFrequentElement(nums);
    
    cout << "The highest occurring element in the array is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n*n) (where n is the size of the array given) – Using two nested loops.
• Space Complexity:O(n) – Using a visited array of size n and a couple of variables.

2️⃣ Hashing (Optimal Approach)

Intuition:

An optimal approach to solve this question will be to use a Hashmap, a data structure that stores key-value pairs.

• Key will denote the element in the array.
• Value will store the frequency of the element in the array.

In C++ it is the unordered_map.

Or we can use hashing with an array, also known as using a “direct address table”

Approach:

• Either take an HashMap (unordered_map) or array.
• Traverse the array and update the frequencies of each element in the hash table.
• Iterate through the hash table to find the element with the highest frequency.
• This approach has a time complexity of O(n), where n is the number of elements in the array, and a space complexity of O(k), where k is the number of distinct elements.

Code:

Using unordered_map:

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

int highestOccurringElement(const std::vector<int>& arr) {
    // Step 1: Create a frequency map to count occurrences of each element
    std::unordered_map<int, int> frequencyMap;

    // Step 2: Populate the frequency map
    for (int num : arr) {
        frequencyMap[num]++;
    }

    // Step 3: Find the element with the highest frequency
    int maxFrequency = 0;
    int mostFrequentElement = arr[0];

    for (const auto& pair : frequencyMap) {
        if (pair.second > maxFrequency) {
            maxFrequency = pair.second;
            mostFrequentElement = pair.first;
        }
    }

    return mostFrequentElement;
}

int main() {
    std::vector<int> arr = {1, 3, 2, 1, 4, 1, 2, 2};
    int result = highestOccurringElement(arr);
    std::cout << "The highest occurring element is: " << result << std::endl;
    return 0;
}

Time and Space Complexity

• Time Complexity: O(n) because we make a single pass to count the frequencies and another pass to find the maximum frequency.
• Space Complexity: O(k), where k is the number of distinct elements in the array (for storing the frequencies in the hash map).

Using Simple Array Hashing:

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

#define SIZE 6 // size of the array
bool visited[SIZE] = {false};
int frequency[SIZE] = {0};

int highestOccurringElement(int arr[], int size) {
    int maxElm = 0;
    int maxFreq = 0;
    
    // Count frequencies of each element in the input array.
    for(int i = 0; i < size; i++){
        if (visited[i] == true){
            continue;
        }
        frequency[arr[i]]++;
    }
    
    // Find the most frequent element
    for (int i = 0; i < size; i++) {
        if (frequency[i] > maxFreq) {
            maxFreq = frequency[i];
            maxElm = i;
        }
    }
    return maxElm;
}

int main()
{
  int arr[SIZE] = {1, 2, 3, 2, 3, 5};

  int highestOccurring = highestOccurringElement(arr, SIZE);
  cout << highestOccurring<<endl;
}

Time and Space Complexity

• Time Complexity: O(n + k), where n is the number of elements in the input array and k is the range of possible values (maxValue + 1).
  • The O(n) term is for iterating through the input array.
  • The O(k) term is for iterating through the frequency array to find the most frequent element.
• Space Complexity: O(k), where k is maxValue + 1, due to the size of the frequency array.

Using Vector (dynamic array):

#include <iostream>
#include <vector>

void countFrequenciesUsingArrayHashing(const std::vector<int>& arr, int maxValue) {
    // Step 1: Create the frequency array of size maxValue + 1 and initialize to 0
    std::vector<int> freq(maxValue + 1, 0);  // Using a vector to handle dynamic sizes

    // Step 2: Count frequencies of each element in the input array
    for (int num : arr) {
        freq[num]++;
    }

    // Step 3: Output frequencies of all elements
    for (int i = 0; i <= maxValue; ++i) {
        if (freq[i] > 0) {
            std::cout << i << ": " << freq[i] << std::endl;
        }
    }
}

int main() {
    std::vector<int> arr = {3, 5, 3, 2, 8, 5, 5, 2};
    int maxValue = 8;  // Assuming we know the maximum value in the array
    countFrequenciesUsingArrayHashing(arr, maxValue);
    return 0;
}

Time and Space Complexity

• Time Complexity: O(n + k), where n is the number of elements in the input array and k is the range of values (maxValue + 1). The O(n) term comes from iterating over the input array, and O(k) comes from iterating over the frequency array.
• Space Complexity: O(k), where k is maxValue + 1, due to the size of the frequency array.