3005. Count Elements With Maximum Frequency
Problem Description
In this problem, we are given an array of positive integers, and we need to find the "total frequencies" of the elements having the "maximum frequency". The frequency of an element is defined by how many times that element appears within the array. In simpler terms, we must:
- Count how many times each unique element appears in the given array.
- Identify the highest frequency - that is, the maximum number of times any element is repeated in the array.
- Add up the frequencies of all the elements that are repeated as many times as the maximum frequency.
- Return this sum as our answer.
This is a problem of calculating occurrences and then working with those counts to determine which numbers are the most common and to what extent.
Intuition
The intuition behind the solution is based on two steps: counting and comparison. The approach goes as follows:
-
Count each element's occurrences: We can use a data structure, like a hash table, to keep track of how many times each element appears in the array. In Python, this can be efficiently done using the
Counter
class from thecollections
module. -
Identify and sum the maximum frequencies: Once we have the counts, we look through them to find the maximum frequency value. With that value in hand, we can then sum up the occurrences of all elements that have this maximum frequency.
The process is based on the simple observation that any element's frequency is as significant as the number of times we find it in the array. By counting all elements first, we then need only compare those counts to find and sum up the highest ones.
Solution Approach
The solution makes use of a counting approach, which is both intuitive and efficient for this type of problem. It leverages the following algorithms, data structures, and patterns:
-
Hash Table (
Counter
from Python'scollections
module): This data structure is ideal for counting instances of elements because it provides constant-time lookups and insertions (O(1)
). We useCounter
to create a hash table where keys are the elements ofnums
and values are their corresponding frequencies.Implementation snippet:
cnt = Counter(nums)
-
Finding Maximum Value: After counting, we need to find the maximum frequency. We can achieve this by utilizing the built-in
max
function to traverse the values in the counter and find the highest count.Implementation snippet:
mx = max(cnt.values())
-
Summing Specific Frequencies: Lastly, we need to return the sum of the frequencies of the elements that are exactly equal to the maximum frequency found. We achieve this by using a generator expression that iterates over the values of our counter and sums up those that equal
mx
.Implementation snippet:
return sum(x for x in cnt.values() if x == mx)
By combining these steps, the solution is able to find the "total frequency" of the maximum frequency elements in nums
. The Counter
simplifies the counting process, max
helps us quickly find the highest frequency, and the generator expression is a Pythonic way to compute the conditional sum we're interested in.
This is a direct approach working well for the problem due to its simplicity and the efficiency of counting and hash table operations in Python.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach described above. Suppose we have the following array of integers:
nums = [2, 3, 3, 2, 5]
First, we shall count each element's occurrences using the Counter
class.
cnt = Counter(nums) # cnt will be Counter({2: 2, 3: 2, 5: 1})
In this step, the Counter
object cnt
gives us {2: 2, 3: 2, 5: 1}
which shows that '2' appears 2 times, '3' appears 2 times, and '5' appears 1 time.
Next, we need to identify the maximum frequency from the Counter
object. In this case, both 2 and 3 have the same highest frequency, which is 2.
mx = max(cnt.values()) # mx will be 2
Here, mx
is the variable holding the maximum frequency, which equals 2.
Finally, we sum the frequencies of all elements that have this maximum frequency. Since the maximum frequency is 2, and elements 2 and 3 both occur twice, we sum these frequencies:
return sum(x for x in cnt.values() if x == mx) # returns 2 + 2 = 4
The generator expression iterates over the values 2, 2, 1
in the cnt
, but only sums those equal to mx
(which is 2), resulting in 2 + 2
, and thus the total frequency sum we return is 4.
Our final result for the nums
array using the steps described in the solution approach is 4. This demonstrates the correctness and efficiency of the described approach in finding the sum of the frequencies of the elements with the maximum frequency in the array.
Solution Implementation
1from collections import Counter
2from typing import List
3
4class Solution:
5 def maxFrequencyElements(self, nums: List[int]) -> int:
6 # Count the frequency of each element in the nums list using Counter
7 frequency_counter = Counter(nums)
8
9 # Find the maximum frequency among all elements
10 max_frequency = max(frequency_counter.values())
11
12 # Calculate the sum of elements that have the maximum frequency
13 # This is the count of elements that appear the most frequently in the list
14 max_frequency_elements_count = sum(frequency for frequency in frequency_counter.values() if frequency == max_frequency)
15
16 return max_frequency_elements_count
17
18# Example usage:
19# solution = Solution()
20# result = solution.maxFrequencyElements([1, 2, 2, 3, 3, 3])
21# print(result) # Output: 3, since '3' appears 3 times, which is the max frequency
22
1class Solution {
2 public int maxFrequencyElements(int[] nums) {
3 int[] frequency = new int[101]; // Array to store the frequency of elements, assuming the values range between 0 and 100
4 // Count the frequency of each number in the given array
5 for (int num : nums) {
6 ++frequency[num];
7 }
8
9 int totalMaxFrequency = 0; // This will hold the sum of the maximum frequencies
10 int maxFrequency = -1; // Store the current maximum frequency found
11
12 // Iterate over the frequency array to find the highest frequency count(s)
13 for (int freq : frequency) {
14 if (maxFrequency < freq) { // Found a new maximum frequency
15 maxFrequency = freq; // Update the maximum frequency
16 totalMaxFrequency = freq; // Reset the total to the current max frequency
17 } else if (maxFrequency == freq) { // Found another frequency count that matches the maximum
18 totalMaxFrequency += freq; // Add to the total the frequency of this value
19 }
20 }
21 return totalMaxFrequency; // Return the sum of the highest frequencies
22 }
23}
24
1#include <vector>
2
3class Solution {
4public:
5 // Function to find the maximum frequency of elements in the given vector
6 int maxFrequencyElements(vector<int>& nums) {
7 int counts[101] = {0}; // Initialize array to store frequencies of elements, assuming elements range from 0 to 100
8 // Count frequency of each element in nums
9 for (int num : nums) {
10 ++counts[num];
11 }
12 int maxFrequency = 0; // Variable to hold the maximum frequency
13 int maxOccurringElementCount = -1; // Helps in tracking the largest count found so far
14
15 // Iterate over the frequency array to find the maximum frequency
16 for (int freq : counts) {
17 if (maxOccurringElementCount < freq) {
18 // New maximum found, update max variables
19 maxOccurringElementCount = freq;
20 maxFrequency = freq;
21 } else if (maxOccurringElementCount == freq) {
22 // If current frequency matches max, accumulate the result
23 maxFrequency += freq;
24 }
25 }
26
27 // Return the maximum frequency of any element in nums
28 return maxFrequency;
29 }
30};
31
1// Function to find the maximum frequency of elements in an array.
2// The input is limited to integers between 0 and 100 inclusive.
3function maxFrequencyElements(nums: number[]): number {
4 // Initialize an array to hold counts for each possible number from 0 to 100.
5 const counts: number[] = new Array(101).fill(0);
6
7 // Populate the counts array with the frequency of each number.
8 for (const num of nums) {
9 ++counts[num];
10 }
11
12 // Initialize variables to store the maximum frequency found and
13 // the sum of frequencies that are equal to the maximum.
14 let maxFrequencySum = 0;
15 let currentMaxFrequency = -1;
16
17 // Iterate through the counts array to find the maximum frequency.
18 for (const frequency of counts) {
19 if (currentMaxFrequency < frequency) {
20 // If the current frequency is higher than the previous maximum,
21 // update the maximum frequency and reset the sum.
22 currentMaxFrequency = frequency;
23 maxFrequencySum = frequency;
24 } else if (currentMaxFrequency === frequency) {
25 // If the current frequency matches the maximum frequency,
26 // add it to the sum.
27 maxFrequencySum += frequency;
28 }
29 }
30
31 // Return the sum of frequencies that are equal to the maximum frequency found.
32 return maxFrequencySum;
33}
34
Time and Space Complexity
Time Complexity
The time complexity of the given code can primarily be broken down into two segments:
-
Constructing the counter
cnt
from the listnums
viaCounter(nums)
, which requires iterating through all the elements innums
. The time complexity for building the counter isO(n)
, wheren
is the length of the listnums
. -
Finding the maximum frequency with
max(cnt.values())
and then summing up instances where the frequency is equal to this maximum frequencysum(x for x in cnt.values() if x == mx)
. The time to findmax(cnt.values())
isO(k)
, wherek
is the number of unique elements innums
. The summing part involves going through these values at most once, which is againO(k)
.
Since k <= n
, both steps are bounded by O(n)
complexity. Therefore, when considering the combined time complexity of these operations, the total time complexity is O(n)
.
Space Complexity
The space complexity is determined by:
-
The space required to store the
cnt
counter, which can contain at mostn
unique elements if all elements ofnums
are unique. Thus, the space complexity due to the counter isO(n)
. -
The space required for variable
mx
is constant,O(1)
.
Given that O(n) + O(1)
simplifies to O(n)
, the overall space complexity of the code is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!