algoadvance

Leetcode 3005. Count Elements With Maximum Frequency

Problem Statement

You are given an integer array arr. Your task is to determine the number of elements in the array that appear with the maximum frequency.

Clarifying Questions

  1. What should be the output if the array is empty?
    • Return 0 since no elements exist in the array.
  2. Are there any constraints on the size of the array or the range of values within it?
    • For optimal performance, we’re assuming the size of the array can be reasonably large, but not exceedingly huge that it can’t fit into memory or be handled in a typical coding interview scenario.
  3. Can the array contain both positive and negative integers?
    • Yes, the array can contain any integer values.

Strategy

  1. Count the Frequency:
    • Use a hashmap (unordered_map in C++) to count the frequency of each element in the array.
  2. Determine Maximum Frequency:
    • Traverse the hashmap to find the maximum frequency.
  3. Count Elements with Maximum Frequency:
    • Traverse the hashmap again to count how many elements have this maximum frequency.

Time Complexity

Here is the C++ code to solve the problem:

Code

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

int countElementsWithMaximumFrequency(const std::vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }

    std::unordered_map<int, int> frequencyMap;

    // Count the frequency of each element
    for (const int &num : arr) {
        frequencyMap[num]++;
    }

    // Find the maximum frequency
    int maxFrequency = 0;
    for (const auto &entry : frequencyMap) {
        if (entry.second > maxFrequency) {
            maxFrequency = entry.second;
        }
    }

    // Count how many elements have this maximum frequency
    int count = 0;
    for (const auto &entry : frequencyMap) {
        if (entry.second == maxFrequency) {
            count++;
        }
    }

    return count;
}

int main() {
    std::vector<int> arr = {1, 3, 3, 1, 2, 4, 1};
    std::cout << "Number of elements with maximum frequency: " << countElementsWithMaximumFrequency(arr) << std::endl;
    return 0;
}

This solution reads the array, counts frequencies, identifies the highest frequency, and then counts how many elements have that frequency, all while maintaining excellent time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI