Count Elements With Maximum Frequency

Easy Arrays & Hashing Hashing Original on LeetCode

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 <= 100
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
Brute forceO(n²)O(n)
Optimal (one-pass counting)O(n)O(1)

1Brute force

TimeO(n²)Each of the n positions rescans all n elements.
SpaceO(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.

  1. For each i, scan the array to get cnt[i] = occurrences of nums[i].
  2. Let best be the maximum of all cnt[i].
  3. 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;
    }
}

2Optimal (one-pass counting)

TimeO(n)One pass, constant work per element.
SpaceO(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.

  1. Make freq[101] and set best = 0, total = 0.
  2. For each x: c = ++freq[x].
  3. If c > best: best = c, total = c.
  4. Else if c == best: total += c.
  5. 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;
    }
}

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.