Count Elements With Maximum Frequency
EasyPrompt
You are given an array nums consisting of positive integers.
Return the total frequencies of elements in nums such that those elements all have the maximum frequency.
The frequency of an element is the number of occurrences of that element in the array.
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 number of elements in the array with maximum frequency is 4.Example 2:
Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most efficient approach, tailored to the problem's constraints (1 <= nums[i] <= 100). Instead of a hash map, we use a simple array of size 101 as a frequency map. This eliminates the overhead of hashing and provides constant-time access for frequency updates, leading to better performance and constant space complexity.
Algorithm
- Create an integer array
freqof size 101, initialized to zeros. - Initialize
maxFreq = 0andtotalFreq = 0. - Iterate through each
numin thenumsarray. - Increment
freq[num]and get itscurrentFreq. - If
currentFreq > maxFreq:- Set
maxFreq = currentFreq. - Set
totalFreq = currentFreq.
- Set
- Else if
currentFreq == maxFreq:- Add
maxFreqtototalFreq.
- Add
- After the loop, return
totalFreq.
Walkthrough
Given the constraint that all numbers in nums are between 1 and 100, we can replace the HashMap with a simple integer array of size 101. This array will act as a direct-access frequency map, where freq[i] stores the frequency of the number i.
The logic is identical to the single-pass hash map approach. We iterate through nums once, maintaining maxFreq and totalFreq variables. For each num:
- We increment
freq[num]. - We check the new frequency
freq[num]againstmaxFreqand updatemaxFreqandtotalFreqaccordingly. This method is faster due to direct array indexing instead of hash computations and has a constant space complexity because the array size is fixed regardless of the input size.
class Solution { public int maxFrequencyElements(int[] nums) { int[] freq = new int[101]; // Constraints: 1 <= nums[i] <= 100 int maxFreq = 0; int totalFreq = 0; for (int num : nums) { freq[num]++; int currentFreq = freq[num]; if (currentFreq > maxFreq) { maxFreq = currentFreq; totalFreq = currentFreq; } else if (currentFreq == maxFreq) { totalFreq += maxFreq; } } return totalFreq; }}Complexity
Time
O(N), for a single pass over the `nums` array. Array access is an O(1) operation.
Space
O(1). The space used by the frequency array is constant (101 integers), regardless of the size of the input array `nums`.
Trade-offs
Pros
Most efficient in terms of both time and space due to the use of a fixed-size array and a single pass.
Simple and clean implementation with no hashing overhead.
Cons
This solution is specific to the given constraints on the range of numbers. It would not be suitable if the numbers could be very large or negative without modification.
This approach involves two main steps. First, we iterate through the input array to count the frequency of each number using a hash map. Second, we iterate through the frequencies we've collected to find the maximum frequency and then calculate the total frequency of elements that have this maximum frequency.
Algorithm
- Create a
HashMap<Integer, Integer>to store the frequency of each number. - Iterate through the input
numsarray. For each number, increment its count in the hash map. - After populating the map, initialize a variable
maxFreqto 0. - Iterate through the values (frequencies) of the map to find the maximum frequency and store it in
maxFreq. - Initialize a result variable
totalFreqto 0. - Iterate through the map's values one more time. If a frequency is equal to
maxFreq, addmaxFreqtototalFreq. - Return
totalFreq.
Walkthrough
In this method, we first perform a complete pass over the nums array to build a frequency map. A HashMap is a suitable data structure for this, where keys are the numbers from the array and values are their frequencies.
Once the map is built, we perform a second pass, this time over the values of the map, to determine the maximum frequency (maxFreq) present.
Finally, a third pass over the map's values is needed. We sum up all frequencies that are equal to maxFreq. This sum gives us the total number of elements that belong to the group of most frequent elements.
import java.util.HashMap;import java.util.Map; class Solution { public int maxFrequencyElements(int[] nums) { Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } if (freqMap.isEmpty()) { return 0; } int maxFreq = 0; for (int freq : freqMap.values()) { if (freq > maxFreq) { maxFreq = freq; } } int totalFreq = 0; for (int freq : freqMap.values()) { if (freq == maxFreq) { totalFreq += freq; } } return totalFreq; }}Complexity
Time
O(N), where N is the number of elements in `nums`. The first loop to build the map takes O(N). The subsequent loops iterate over the unique elements (at most N), so the total time is dominated by the first pass, resulting in O(N).
Space
O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity becomes O(N).
Trade-offs
Pros
Conceptually simple and easy to follow.
It's a general solution that works for any range of input numbers, not just the constrained range of 1-100.
Cons
Requires multiple passes over the frequency data, making it slightly less efficient than a single-pass approach.
Uses a hash map, which can have higher overhead than a simple array for a constrained range of values.
This approach optimizes the two-pass method by calculating the result in a single pass through the input array. We maintain the current maximum frequency and the total frequency of elements with that maximum frequency as we build the frequency map.
Algorithm
- Create a
HashMap<Integer, Integer>calledfreqMap. - Initialize
maxFreq = 0andtotalFreq = 0. - Iterate through each
numin thenumsarray. - Increment the frequency of
numinfreqMapand get itscurrentFreq. - If
currentFreq > maxFreq:- Set
maxFreq = currentFreq. - Set
totalFreq = currentFreq.
- Set
- Else if
currentFreq == maxFreq:- Add
maxFreqtototalFreq.
- Add
- After the loop, return
totalFreq.
Walkthrough
We can solve the problem more efficiently by processing the array in a single pass. We use a HashMap to store frequencies, but we also maintain two variables on the fly: maxFreq to track the maximum frequency seen so far, and totalFreq to store the result.
As we iterate through the nums array, for each number:
- We increment its frequency in the map and get the updated frequency,
currentFreq. - We compare
currentFreqwithmaxFreq.- If
currentFreq > maxFreq, we've found a new most frequent element. We updatemaxFreqtocurrentFreqand resettotalFreqto be justcurrentFreq. - If
currentFreq == maxFreq, we've found another element with the same maximum frequency. We add its frequency (maxFreq) tototalFreq. - If
currentFreq < maxFreq, we do nothing.
- If
After the single loop finishes, totalFreq will hold the correct result.
import java.util.HashMap;import java.util.Map; class Solution { public int maxFrequencyElements(int[] nums) { Map<Integer, Integer> freqMap = new HashMap<>(); int maxFreq = 0; int totalFreq = 0; for (int num : nums) { int currentFreq = freqMap.getOrDefault(num, 0) + 1; freqMap.put(num, currentFreq); if (currentFreq > maxFreq) { maxFreq = currentFreq; totalFreq = currentFreq; // Reset total, this is the first element with the new max frequency } else if (currentFreq == maxFreq) { totalFreq += maxFreq; // Add another element with the same max frequency } } return totalFreq; }}Complexity
Time
O(N), as we iterate through the input array only once.
Space
O(U), where U is the number of unique elements. In the worst case, this is O(N).
Trade-offs
Pros
More efficient than the two-pass approach as it processes the array in a single pass.
Still a general solution that works for any range of input numbers.
Cons
The logic inside the loop is slightly more complex than in the two-pass approach.
Still relies on a hash map, which might not be the most optimal data structure given the problem's constraints.
Solutions
Solution
class Solution {public int maxFrequencyElements(int[] nums) { int[] cnt = new int[101]; for (int x : nums) { ++cnt[x]; } int ans = 0, mx = -1; for (int x : cnt) { if (mx < x) { mx = x; ans = x; } else if (mx == x) { ans += x; } } return ans; }}class Solution {public: int maxFrequencyElements(vector<int> &nums) { int cnt[101]{}; for (int x : nums) { ++cnt[x]; } int ans = 0, mx = -1; for (int x : cnt) { if (mx < x) { mx = x; ans = x; } else if (mx == x) { ans += x; } } return ans; }};class Solution: def maxFrequencyElements(self, nums: List[int]) -> int: cnt = Counter(nums) mx = max(cnt . values()) return sum(x for x in cnt . values() if x == mx)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.