Counting with a hash map

"Which value shows up most?" sounds like a job for two loops: pick a value, then count it. That works on a small array and times out on a large one.

The fix is the move behind dozens of later problems: count everything once, in one pass, then answer from the counts.

Read the problem

Ask these before you code:

• A tie? The statement answers it: the smallest value wins. Plan the comparison for it.
• All values different? Every count is 1, so it is a tie of all. Return the smallest value.
• One item? Return it.
• What range? Values from 1 to 10⁴. Keep that in mind: it opens a second way to count.

n reaches 10⁵. O(n²) is 10¹⁰ steps, so aim for O(n log n) or better.

Brute force: count each value from scratch

For each item, walk the whole array and count how often it appears. Keep the best so far.

JavaPythonTypeScript

int mostFrequent(int[] nums) {
    int best = -1;
    int bestCount = 0;
    for (int x : nums) {
        int count = 0;
        for (int y : nums) if (y == x) count++; // count x from scratch
        if (count > bestCount || (count == bestCount && x < best)) {
            best = x;
            bestCount = count;
        }
    }
    return best;
}

The outer loop runs n times. For each, the inner loop reads all n items.

So n × n, O(n²). For n = 10⁵ that is 10¹⁰ comparisons: far too slow.

The key insight: keep a tally

The brute force counts 4 three times over. Each count throws away what the last one learned.

Think of counting votes on a whiteboard. You read each ballot once and add a mark next to its name.

At the end you read the totals. Nobody re-reads the pile for each name.

┌────────────────────────────────────────────┐
│                                            │
│           nums  4  1  4  2  1  4           │
│                                            │
│           value │ marks │ count            │
│           ──────┼───────┼──────            │
│             4   │ ▓▓▓   │   3              │
│             1   │ ▓▓    │   2              │
│             2   │ ▓     │   1              │
│                                            │
└────────────────────────────────────────────┘

A hash map is that whiteboard. Here the key is the value from the array, and what it stores is the count.

Optimal: one pass with a hash map

1. Make an empty hash map of value to count.
2. For each item, add 1 to its count. A value not seen yet starts from 0.
3. Walk the map once. Keep the value with the highest count, and the smaller value on a tie.

JavaPythonTypeScript

int mostFrequent(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    int best = -1;
    int bestCount = 0;
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        int value = e.getKey();
        int c = e.getValue();
        if (c > bestCount || (c == bestCount && value < best)) {
            best = value;
            bestCount = c;
        }
    }
    return best;
}

• A new value has no entry yet, so each language reads it as 0: getOrDefault(x, 0) in Java, count.get(x, 0) in Python, count.get(x) ?? 0 in TypeScript (where get returns undefined).
• Shortcuts: count.merge(x, 1, Integer::sum) in Java. In Python, collections.Counter(nums) builds the whole map in one call.
• c == bestCount && value < best: the tie rule from the statement, in one condition.
• In Java, copy counts into int before you compare them, as above. Two Integer objects above 127 compared with == compare references, not values.
• Time: n updates, then one walk over k distinct values. O(n + k), which is O(n).
• Space: one entry per distinct value, O(k).

When the values are small: an array of counts

The limits say every value is between 1 and 10⁴. So an array can play the map: the value is the index.

┌────────────────────────────────────────────┐
│                                            │
│    value (index)   0   1   2   3   4       │
│    count           0   2   1   0   3       │
│                        ▲           ▲       │
│                     two 1s     three 4s    │
│                                            │
└────────────────────────────────────────────┘

JavaPythonTypeScript

int[] count = new int[10001];
for (int x : nums) count[x]++;

Walk the indexes from small to large and keep the first highest count: ties go to the smaller value for free. 10,001 slots is tiny. For values up to 10⁹, or negative values, or strings, use a hash map.

Side by side

Here k is the number of distinct values, and the range is the largest value allowed.

More answers from the same counts

Once the counts exist, the other problems on this lesson's list are a short walk over them:

• Second Highest Occurring Element. Find the highest count, then the highest count below it. Return the smallest value with that second count. If every value has the same count, there is no second, so return -1. For [1, 2, 2, 3, 3, 3], the answer is 2.
• Sum of Highest and Lowest Frequency. Add the largest and smallest counts. For [1, 2, 2, 3, 3, 3], that is 3 + 1 = 4.

JavaPythonTypeScript

int high = Collections.max(count.values());
int low = Collections.min(count.values());
return high + low;

Counting letters works the same way. The next lesson's anagram check counts the letters of two words and compares the tallies.

How to spot this pattern

The one line to remember:

JavaPythonTypeScript

for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);

take U forwardYouTube

Read more

• Map on MDN, including how it differs from a plain object
• Hash table on Wikipedia, for how a map finds a key in about one step
• MapReduce: Simplified Data Processing on Large Clusters by Jeffrey Dean and Sanjay Ghemawat, the word count example
• Highest Occurring Element in an Array on takeUforward, to solve it yourself

Next: string basics, where palindromes, anagrams and rotations reuse two pointers and counting.