Premium

Frequency Map

Basic Algorithms
≈ 2 min read

The value as a key, the count as data

A frequency map stores the number of occurrences for each value. The value itself becomes the key, while the counter becomes the value in the Map. This technique works for numbers, characters, strings, and any other objects that can be used as keys. 

Map<Integer, Integer> frequency = new HashMap<>();

for (int value : numbers) {
    int count = frequency.getOrDefault(value, 0);
    frequency.put(value, count + 1);
}

On the first occurrence of a key, getOrDefault() returns 0. On later occurrences, the already accumulated counter is read from the map and increased by one. After one pass, the map contains the frequency of every distinct value.

What does it cost

If the array contains n elements, the loop performs n iterations. With an expected O(1) cost for HashMap operations, building the map takes O(n) time. If there are k distinct values, the additional memory usage is O(k).

This is especially useful when, after counting, we need to answer questions such as “how many times does 7 occur?”, “which values appear more than once?”, or “do two sequences have the same frequency distribution?”.

A compact form with merge

The same counter can be updated with the merge() method. It inserts the initial value 1 if the key is absent, and for an existing key combines the old and new values using the supplied function. 

for (int value : numbers) {
    frequency.merge(value, 1, Integer::sum);
}

Both forms solve the same problem. In algorithms, the important part is the “element → count” model; the exact way the counter is updated is mainly a matter of readability and coding style.

A frequency map stores data only for values that actually occur. This is often more memory-efficient than a large counter array when the possible value range is huge but the input contains only a small part of it.
Back Next