LeetCode Problem 3005

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

LeetCode 3005 - Count Elements With Maximum Frequency

Problem Understanding

The problem gives us an integer array nums, where every value is positive. We need to determine which elements appear most frequently, then return the total number of occurrences contributed by all such elements.

In other words, we first compute the frequency of every distinct number in the array. After that, we identify the maximum frequency value. Finally, we add together the frequencies of every element whose frequency equals that maximum.

Consider the array:

[1,2,2,3,1,4]

The frequencies are:

• 1 -> 2
• 2 -> 2
• 3 -> 1
• 4 -> 1

The maximum frequency is 2. Both 1 and 2 have this frequency, so the answer becomes:

2 + 2 = 4

The input represents a small array of integers. The constraints tell us:

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

These limits are very small, which means almost any reasonable solution will pass comfortably. However, the goal is still to write a clean and efficient implementation.

A few important observations and edge cases arise immediately:

• The array always contains at least one element.
• Multiple elements may share the same maximum frequency.
• Every element might appear exactly once.
• One element may dominate the array completely.
• Since values are small positive integers, either a hash map or a counting array works well.

The problem guarantees valid positive integers, so we do not need to handle empty arrays or invalid values.

Approaches

Brute Force Approach

A straightforward solution is to compute the frequency of every element by repeatedly scanning the array.

For each element in nums, we could count how many times it appears by looping through the entire array again. While doing this, we track the maximum frequency seen so far. After determining the maximum frequency, we scan again and sum the frequencies of elements that match that maximum.

This works because exhaustive counting guarantees accurate frequencies for every value. However, the repeated scanning creates unnecessary work.

If the array has n elements, counting each element by scanning the full array costs O(n) time, and doing that for all elements costs O(n^2) overall.

Even though the constraints are small enough for this to pass, it is inefficient compared to a frequency map solution.

Optimal Approach

The key insight is that frequency counting is exactly what hash maps are designed for.

Instead of repeatedly scanning the array, we store the count of each number as we iterate once through the array. After building the frequency map, we determine the maximum frequency. Then we sum all frequencies equal to that maximum.

This avoids redundant work because each element is processed only once during counting.

A hash map provides average O(1) insertion and lookup time, making the overall algorithm linear.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the array to count occurrences
Optimal	O(n)	O(n)	Uses a hash map to count frequencies efficiently

Algorithm Walkthrough

1. Create a hash map called frequency_map.

This map stores how many times each number appears. The key is the number itself, and the value is its frequency. 2. Traverse the array once and update frequencies.

For every number in nums, increment its count in the hash map. After this step, we know the exact frequency of every distinct element. 3. Find the maximum frequency.

Iterate through the values in the frequency map and determine the largest frequency value present. 4. Compute the total frequency of elements with maximum frequency.

Traverse the frequency map again. Whenever a frequency equals the maximum frequency, add it to the answer. 5. Return the final answer.

This value represents the total number of occurrences contributed by all elements tied for highest frequency.

Why it works

The algorithm works because the frequency map accurately records the occurrence count for every distinct number. The maximum frequency identifies which elements appear most often. Summing all frequencies equal to that maximum gives exactly the total number of array elements belonging to the most frequent group.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        frequency_map = Counter(nums)

        max_frequency = max(frequency_map.values())

        total = 0

        for frequency in frequency_map.values():
            if frequency == max_frequency:
                total += frequency

        return total

The implementation begins by using Python's Counter class from the collections module. This automatically builds a frequency map where each number is associated with its occurrence count.

Next, the code computes the maximum frequency using max(frequency_map.values()). Since the array is guaranteed to contain at least one element, this operation is always safe.

The variable total stores the running answer. We iterate through every frequency in the map, and whenever a frequency matches the maximum frequency, we add it to total.

Finally, the function returns the accumulated result.

This implementation directly follows the algorithm steps described earlier and remains concise while preserving readability.

Go Solution

func maxFrequencyElements(nums []int) int {
	frequencyMap := make(map[int]int)

	for _, num := range nums {
		frequencyMap[num]++
	}

	maxFrequency := 0

	for _, frequency := range frequencyMap {
		if frequency > maxFrequency {
			maxFrequency = frequency
		}
	}

	total := 0

	for _, frequency := range frequencyMap {
		if frequency == maxFrequency {
			total += frequency
		}
	}

	return total
}

The Go solution mirrors the Python approach closely. A map[int]int is used instead of Python's Counter.

Go does not provide a built in frequency counting utility equivalent to Counter, so we manually increment counts inside the loop.

The rest of the implementation follows the same logic:

• Find the maximum frequency
• Sum all frequencies equal to that maximum
• Return the result

No special handling for nil or empty slices is necessary because the problem guarantees at least one element in the input array.

Integer overflow is not a concern because the maximum possible answer is only 100.

Worked Examples

Example 1

Input: nums = [1,2,2,3,1,4]

Step 1: Build frequency map

Current Number	Frequency Map
1	{1: 1}
2	{1: 1, 2: 1}
2	{1: 1, 2: 2}
3	{1: 1, 2: 2, 3: 1}
1	{1: 2, 2: 2, 3: 1}
4	{1: 2, 2: 2, 3: 1, 4: 1}

Step 2: Find maximum frequency

The frequencies are:

[2, 2, 1, 1]

Maximum frequency:

2

Step 3: Sum matching frequencies

Element	Frequency	Matches Max?	Running Total
1	2	Yes	2
2	2	Yes	4
3	1	No	4
4	1	No	4

Final answer:

4

Example 2

Input: nums = [1,2,3,4,5]

Step 1: Build frequency map

Current Number	Frequency Map
1	{1: 1}
2	{1: 1, 2: 1}
3	{1: 1, 2: 1, 3: 1}
4	{1: 1, 2: 1, 3: 1, 4: 1}
5	{1: 1, 2: 1, 3: 1, 4: 1, 5: 1}

Step 2: Find maximum frequency

All frequencies are:

[1, 1, 1, 1, 1]

Maximum frequency:

1

Step 3: Sum matching frequencies

Element	Frequency	Matches Max?	Running Total
1	1	Yes	1
2	1	Yes	2
3	1	Yes	3
4	1	Yes	4
5	1	Yes	5

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed a constant number of times
Space	O(n)	The hash map may store every distinct element

The algorithm performs three linear passes:

• One pass to build the frequency map
• One pass to find the maximum frequency
• One pass to compute the total

Since each pass is linear, the total runtime remains O(n).

The extra space comes from the hash map. In the worst case, every element is distinct, so the map stores n entries.

Test Cases

from typing import List
from collections import Counter

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        frequency_map = Counter(nums)

        max_frequency = max(frequency_map.values())

        total = 0

        for frequency in frequency_map.values():
            if frequency == max_frequency:
                total += frequency

        return total

solution = Solution()

assert solution.maxFrequencyElements([1, 2, 2, 3, 1, 4]) == 4
# Multiple elements share maximum frequency

assert solution.maxFrequencyElements([1, 2, 3, 4, 5]) == 5
# Every element appears once

assert solution.maxFrequencyElements([7]) == 1
# Single element array

assert solution.maxFrequencyElements([5, 5, 5, 5]) == 4
# One element dominates entire array

assert solution.maxFrequencyElements([1, 1, 2, 2, 3, 3]) == 6
# All elements tied with same frequency

assert solution.maxFrequencyElements([1, 1, 1, 2, 2, 3]) == 3
# Only one element has maximum frequency

assert solution.maxFrequencyElements([4, 4, 2, 2, 3]) == 4
# Two elements tied for maximum frequency

assert solution.maxFrequencyElements([100] * 100) == 100
# Maximum constraint size with identical elements

assert solution.maxFrequencyElements(list(range(1, 101))) == 100
# Maximum constraint size with all unique elements

Test	Why
[1,2,2,3,1,4]	Validates multiple maximum frequency elements
[1,2,3,4,5]	Validates all unique values
[7]	Tests smallest valid input
[5,5,5,5]	Tests single repeated value
[1,1,2,2,3,3]	Tests all elements tied
[1,1,1,2,2,3]	Tests one clear maximum
[4,4,2,2,3]	Tests partial tie for maximum
[100] * 100	Tests upper bound with repeated values
range(1,101)	Tests upper bound with all distinct values

Edge Cases

One important edge case is a single element array, such as [7]. A careless implementation might assume multiple elements exist or fail when computing the maximum frequency. In this implementation, the frequency map contains one entry with frequency 1, and the algorithm correctly returns 1.

Another important case occurs when all elements are unique, such as [1,2,3,4,5]. Every frequency equals 1, which is also the maximum frequency. The algorithm correctly sums all frequencies and returns the entire array length.

A third edge case is when one value dominates the array completely, such as [5,5,5,5]. Some incorrect implementations accidentally count the number of distinct elements with maximum frequency instead of summing their frequencies. This implementation avoids that mistake by adding the frequency value itself, producing the correct answer 4.

Another subtle case occurs when several elements tie for the maximum frequency, such as [1,1,2,2,3,3]. The algorithm correctly identifies that all three elements share the maximum frequency of 2, then sums them to produce 6.