3005. Count Elements With Maximum Frequency

EasyArrayHash TableCounting
Leetcode Link

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:

  1. Count how many times each unique element appears in the given array.
  2. Identify the highest frequency - that is, the maximum number of times any element is repeated in the array.
  3. Add up the frequencies of all the elements that are repeated as many times as the maximum frequency.
  4. 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:

  1. 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 the collections module.

  2. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement priority queue?

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:

  1. Hash Table (Counter from Python's collections module): This data structure is ideal for counting instances of elements because it provides constant-time lookups and insertions (O(1)). We use Counter to create a hash table where keys are the elements of nums and values are their corresponding frequencies.

    Implementation snippet:

    1cnt = Counter(nums)

  2. 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:

    1mx = max(cnt.values())

  3. 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:

    1return 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's go through an example to illustrate the solution approach described above. Suppose we have the following array of integers:

1nums = [2, 3, 3, 2, 5]

First, we shall count each element's occurrences using the Counter class.

1cnt = 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.

1mx = 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:

1return 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
Not Sure What to Study? Take the 2-min Quiz：

Which of the following array represent a max heap?

Time and Space Complexity

Time Complexity

The time complexity of the given code can primarily be broken down into two segments:

  1. Constructing the counter cnt from the list nums via Counter(nums), which requires iterating through all the elements in nums. The time complexity for building the counter is O(n), where n is the length of the list nums.

  2. Finding the maximum frequency with max(cnt.values()) and then summing up instances where the frequency is equal to this maximum frequency sum(x for x in cnt.values() if x == mx). The time to find max(cnt.values()) is O(k), where k is the number of unique elements in nums. The summing part involves going through these values at most once, which is again O(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:

  1. The space required to store the cnt counter, which can contain at most n unique elements if all elements of nums are unique. Thus, the space complexity due to the counter is O(n).

  2. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫