Count Elements With Maximum Frequency
Count Elements With Maximum Frequency is a easy arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (one-pass counting), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
You are given an array nums of positive integers. The frequency of a value is how many times it occurs in nums.
Find the highest frequency of any value, then return the total number of elements in nums whose value has that highest frequency.
Examples
Example 1
- Input
nums = [7, 3, 7, 9, 3, 2]- Output
4- Why
- 7 and 3 both appear twice, the highest count. Together they cover 2 + 2 = 4 elements.
Example 2
- Input
nums = [6, 1, 8]- Output
3- Why
- Every value appears once, so all three elements share the maximum frequency.
Example 3
- Input
nums = [5, 5, 5, 4, 4]- Output
3- Why
- Only 5 reaches the top count of 3.
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 100
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(n) |
| Optimal (one-pass counting) | O(n) | O(1) |
1Brute force
O(n²)Each of the n positions rescans all n elements.O(n)One count per position.For every position, count how many times its value appears by scanning the whole array. Track the highest count, then add up the positions whose value has that count.
- For each i, scan the array to get cnt[i] = occurrences of nums[i].
- Let best be the maximum of all cnt[i].
- Return how many positions i have cnt[i] == best (each such position is one element of a top-frequency value).
class Solution {
public int maxFrequencyElements(int[] nums) {
int n = nums.length;
int[] cnt = new int[n];
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (nums[j] == nums[i]) cnt[i]++;
}
best = Math.max(best, cnt[i]);
}
int total = 0;
for (int i = 0; i < n; i++) {
if (cnt[i] == best) total++;
}
return total;
}
}class Solution:
def maxFrequencyElements(self, nums: List[int]) -> int:
n = len(nums)
cnt = [0] * n
best = 0
for i in range(n):
for j in range(n):
if nums[j] == nums[i]:
cnt[i] += 1
best = max(best, cnt[i])
total = 0
for i in range(n):
if cnt[i] == best:
total += 1
return totalclass Solution {
public:
int maxFrequencyElements(vector<int>& nums) {
int n = nums.size();
vector<int> cnt(n, 0);
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (nums[j] == nums[i]) cnt[i]++;
}
best = max(best, cnt[i]);
}
int total = 0;
for (int i = 0; i < n; i++) {
if (cnt[i] == best) total++;
}
return total;
}
};function maxFrequencyElements(nums) {
const n = nums.length;
const cnt = new Array(n).fill(0);
let best = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (nums[j] === nums[i]) cnt[i]++;
}
best = Math.max(best, cnt[i]);
}
let total = 0;
for (let i = 0; i < n; i++) {
if (cnt[i] === best) total++;
}
return total;
}2Optimal (one-pass counting)
O(n)One pass, constant work per element.O(1)The count array has a fixed size of 101 because values are at most 100.Count values in a small array indexed by value. While counting, keep the current top frequency best and the running answer total. When a value's count beats best, it becomes the only top value, so total = best = count. When it ties best, another top value appears, so add best to total.
- Make freq[101] and set best = 0, total = 0.
- For each x: c = ++freq[x].
- If c > best: best = c, total = c.
- Else if c == best: total += c.
- Return total.
class Solution {
public int maxFrequencyElements(int[] nums) {
int[] freq = new int[101];
int best = 0, total = 0;
for (int x : nums) {
int c = ++freq[x];
if (c > best) {
best = c;
total = c;
} else if (c == best) {
total += c;
}
}
return total;
}
}class Solution:
def maxFrequencyElements(self, nums: List[int]) -> int:
freq = [0] * 101
best = 0
total = 0
for x in nums:
freq[x] += 1
c = freq[x]
if c > best:
best = c
total = c
elif c == best:
total += c
return totalclass Solution {
public:
int maxFrequencyElements(vector<int>& nums) {
vector<int> freq(101, 0);
int best = 0, total = 0;
for (int x : nums) {
int c = ++freq[x];
if (c > best) {
best = c;
total = c;
} else if (c == best) {
total += c;
}
}
return total;
}
};function maxFrequencyElements(nums) {
const freq = new Array(101).fill(0);
let best = 0, total = 0;
for (const x of nums) {
const c = ++freq[x];
if (c > best) {
best = c;
total = c;
} else if (c === best) {
total += c;
}
}
return total;
}Edge cases to test
- A single element: the answer is 1
- All values distinct: the answer is the array length
- All values equal: the answer is the array length
- Several values tie for the top count
Hints
Hint 1
First find how often each value occurs.
Hint 2
The answer is (highest count) × (number of values that reach it). Can you keep both while counting, in one pass?
FAQ
What is the best time complexity for Count Elements With Maximum Frequency?
Optimal (one-pass counting) runs in O(n) time and O(1) extra space. One pass, constant work per element.
Which pattern does Count Elements With Maximum Frequency use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.
Is there a brute force solution for Count Elements With Maximum Frequency?
Yes. Brute force takes O(n²) time and O(n) space. For every position, count how many times its value appears by scanning the whole array.
Which edge cases should I test for Count Elements With Maximum Frequency?
A single element: the answer is 1; All values distinct: the answer is the array length; All values equal: the answer is the array length; Several values tie for the top count.