Count Elements With Maximum Frequency

Difficulty: Easy | Acceptance: 79.80% | Paid: No Topics: Array, Hash Table, Counting

You are given an array nums consisting of positive integers.

Return the total frequency of elements in nums that have the maximum frequency.

The frequency of an element is the number of times it appears in the array.

Examples

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 total frequency of elements with maximum frequency is 2 + 2 = 4.

Example 2:

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

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100

• Hash Map Frequency Counting
• Single Pass Optimization
• Fixed Array Counting
• Sorting

Hash Map Frequency Counting

Intuition We can iterate through the array to count the frequency of each element using a hash map. Once we have all frequencies, we determine the maximum frequency value. Finally, we sum the frequencies of all elements that match this maximum value.

Steps

• Initialize a hash map to store element frequencies.
• Iterate through the input array, incrementing the count for each element in the map.
• Find the maximum value among all frequencies in the map.
• Iterate through the map values again, summing up all values that equal the maximum frequency.

from typing import List
from collections import defaultdict

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        freq = defaultdict(int)
        for num in nums:
            freq[num] += 1
        
        max_freq = 0
        for count in freq.values():
            max_freq = max(max_freq, count)
            
        total = 0
        for count in freq.values():
            if count == max_freq:
                total += count
                
        return total

Complexity

• Time: O(n) where n is the number of elements in the array.
• Space: O(n) to store the frequency map.
• Notes: This approach requires two passes over the map (one to find max, one to sum), but is generally efficient.

Single Pass Optimization

Intuition We can optimize the previous approach by tracking the maximum frequency and the total count of elements with that frequency in a single pass through the array. As we update the frequency of an element, we check if it affects the global maximum.

Steps

• Initialize a hash map, maxFreq to 0, and total to 0.
• Iterate through the array:
  • Increment the frequency of the current number.
  • If the new frequency is greater than maxFreq, update maxFreq and reset total to this new frequency.
  • If the new frequency equals maxFreq, add this frequency to total.

from typing import List
from collections import defaultdict

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        freq = defaultdict(int)
        max_freq = 0
        total = 0
        
        for num in nums:
            freq[num] += 1
            count = freq[num]
            
            if count > max_freq:
                max_freq = count
                total = count
            elif count == max_freq:
                total += count
                
        return total

Complexity

• Time: O(n) where n is the number of elements in the array.
• Space: O(n) to store the frequency map.
• Notes: This is the most optimal approach for the general case, combining counting and aggregation in one pass.

Fixed Array Counting

Intuition Given the constraint 1 <= nums[i] <= 100, the range of possible values is very small and fixed. We can use a fixed-size array (bucket) of size 101 instead of a hash map to count frequencies. This avoids the overhead of hashing and is slightly faster.

Steps

• Initialize an integer array freq of size 101 with zeros.
• Iterate through nums, incrementing the index corresponding to the value.
• Iterate through the freq array to find the maximum frequency.
• Iterate through freq again to sum all values equal to the maximum frequency.

from typing import List

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        freq = [0] * 101
        for num in nums:
            freq[num] += 1
        
        max_freq = max(freq)
        return sum(count for count in freq if count == max_freq)

Complexity

• Time: O(n + k) where n is the array length and k is the value range (101). Since k is constant, this is O(n).
• Space: O(k) for the fixed array, which is O(1) constant space.
• Notes: This is highly efficient for this specific problem due to the tight constraints on input values.

Sorting

Intuition If we sort the array, identical elements will be grouped together. We can then iterate through the sorted array, counting the length of consecutive runs of the same number. We keep track of the maximum run length found so far and the sum of lengths of runs that match this maximum.

Steps

• Sort the input array.
• Initialize maxFreq, total, and currentCount to 0.
• Iterate through the sorted array:
  • If the current number is the same as the previous, increment currentCount.
  • Else, reset currentCount to 1.
  • If currentCount > maxFreq, update maxFreq and set total to currentCount.
  • Else if currentCount == maxFreq, add currentCount to total.

from typing import List

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        nums.sort()
        max_freq = 0
        total = 0
        curr_count = 0
        
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                curr_count += 1
            else:
                curr_count = 1
            
            if curr_count > max_freq:
                max_freq = curr_count
                total = curr_count
            elif curr_count == max_freq:
                total += curr_count
                
        return total

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(1) or O(n) depending on the sorting algorithm’s memory usage.
• Notes: While valid, this is less efficient than the counting approaches for this specific problem.