Problem Statement

Given an array nums consisting of positive integers, we need to return the total count of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is defined as the number of occurrences of that element in the array.

Example Scenarios:

Let's explore a couple of example scenarios to better understand the problem:

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2, which is the maximum frequency in the array.
So the number of elements in the array with the maximum frequency is 4.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1, which is the maximum frequency.
So the number of elements in the array with the maximum frequency is 5.

Constraints

• The length of the array nums is between 1 and 100.
• Each element in nums is a positive integer between 1 and 100.

Approach:

To Solve this problem efficiently, we can follow these steps:

1. Count the frequency of each element in the array.
2. Find the maximum frequency among all elements.
3. Count how many elements have the maximum frequency.

Code

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

using namespace std;

int countMaxFrequencyElements(const vector<int>& nums) {
    unordered_map<int, int> frequencyMap;
    int maxFrequency = 0;

    // Step 1: Count frequencies of each element
    for (int num : nums) {
        frequencyMap[num]++;
        maxFrequency = max(maxFrequency, frequencyMap[num]);
    }

    // Step 2: Count elements with maximum frequency
    int maxFrequencyCount = 0;
    for (const auto& pair : frequencyMap) {
        if (pair.second == maxFrequency) {
            maxFrequencyCount++;
        }
    }

    return maxFrequencyCount * maxFrequency;
}

int main() {
    // Example 1
    vector<int> nums1 = {1, 2, 2, 3, 1, 4};
    cout << "Output (Example 1): " << countMaxFrequencyElements(nums1) << endl;

    // Example 2
    vector<int> nums2 = {1, 2, 3, 4, 5};
    cout << "Output (Example 2): " << countMaxFrequencyElements(nums2) << endl;

    return 0;
}

Output

Output (Example 1): 4
Output (Example 2): 5

Complexity Analysis

Time Complexity: O(n)

• Calculating the frequency of each element takes O(n)
• Counting elements with the maximum frequency takes O(m), where m is the number of distinct elements in the array. In the worst case, m could be equal to n.
• Overall, when we add the time complexities of both steps, we get a total time complexity of O(n + n), which simplifies to O(2n). However, in big O notation, we ignore constant factors, so the time complexity is effectively O(n).

Space Complexity: O(n)

• We use an unordered map to store the frequencies of elements in the array.