Hash Map Frequency Patterns

Description

"Have I seen this value before, and how many times?" Nested loops answer that in O(n²). A hash map answers each question in O(1) on average, which turns most brute-force counting into a single pass. This skill covers counting with a map, using a set as an index, voting algorithms that need no map at all, and what the map does inside. That last part tells you when its O(1) stops being true.

We'll go from simple to more technical:

1. The pattern: count in one pass with a map (getOrDefault / merge / Counter).
2. A second flavor: a set as an index (longest consecutive run) and voting (majority element).
3. Where frequency counting runs in production (analytics, deduplication, rate limits).
4. What breaks it: bad keys, mutated keys, fake signatures, unboxing, unbounded growth.

The approach

Map<Integer, Integer> counts = new HashMap<>();
for (int x : nums) {
    counts.merge(x, 1, Integer::sum);          // or counts.getOrDefault(x, 0) + 1
}
for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
    if (e.getValue() > nums.length / 2) return e.getKey();   // e.g. the majority element
}

def majority_by_count(nums: list[int]) -> int:
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1       # or: counts = collections.Counter(nums)
    for value, c in counts.items():
        if c > len(nums) // 2:
            return value                       # e.g. the majority element
    return -1

merge (or getOrDefault) handles the first sighting: counts.put(x, counts.get(x) + 1) throws NullPointerException there, because get returns null and unboxing null fails. Compare counts with equals or as ints - two Integer objects compare equal with == up to 127 (a cached range) and unequal from 128 on.

Python has the same two traps under other names. counts[x] += 1 on a plain dict raises KeyError at the first sighting - use counts.get(x, 0) + 1, collections.Counter or defaultdict(int). And == compares ints by value, but is compares identity: CPython caches -5 to 256, so a is b works on small counts and fails on large ones, exactly like Java's Integer ==.

Inside, hashCode() picks a bucket; keys that land in the same bucket are kept together and told apart with equals(). When the map holds more than 0.75 x its capacity, it doubles the table and redistributes every entry. Since Java 8, a bucket that reaches 8 entries (in a table of at least 64 buckets) turns into a red-black tree. So lookups are O(1) on average, and degrade toward O(n) only when many keys collide - O(log n) for colliding keys that are Comparable. Python's dict gets the same average O(1) differently: one flat table probed by open addressing (no buckets, no trees), resized once it's two-thirds full - and since 3.7 it keeps insertion order.

A second flavor: a set as an index, and a vote instead of a map

Two of this skill's problems need less than a full count.

Longest consecutive run only asks "is x + 1 present?", which a HashSet answers in O(1):

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int best = 0;
    for (int x : set) {
        if (set.contains(x - 1)) continue;          // not the start of a run - its run is counted elsewhere
        int len = 1;
        while (set.contains(x + len)) len++;
        best = Math.max(best, len);
    }
    return best;
}

def longest_consecutive(nums: list[int]) -> int:
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 in values:
            continue                           # not the start of a run - its run is counted elsewhere
        length = 1
        while x + length in values:
            length += 1
        best = max(best, length)
    return best

Starting only at the first value of each run means every value is walked at most once more, so the whole thing is O(n). Without the check, 1..n costs O(n^2).

Majority element (more than n / 2 copies) needs no map at all. Boyer-Moore voting keeps one candidate and a counter:

int majorityElement(int[] nums) {
    int candidate = 0, count = 0;
    for (int x : nums) {
        if (count == 0) candidate = x;              // adopt a new candidate
        count += (x == candidate) ? 1 : -1;         // a different value cancels one vote
    }
    return candidate;                               // correct when a majority is guaranteed
}

def majority_element(nums: list[int]) -> int:
    candidate, count = 0, 0
    for x in nums:
        if count == 0:
            candidate = x                      # adopt a new candidate
        count += 1 if x == candidate else -1   # a different value cancels one vote
    return candidate                           # correct when a majority is guaranteed

Each decrement pairs one copy of the candidate with one different value, and a value with more than half the elements can't be paired away completely. For "more than n / 3", keep two candidates - and count them again afterwards, because voting always leaves candidates: on [1, 2, 3, 4, 5] it ends with 4 and 5, and neither qualifies.

Where you'll see it

Rate limiting per API key, deduplicating events by ID and top-K analytics are all "count by key, then act on the counts" - backed by Redis instead of an in-process map once the counts must be shared or survive restarts. Grouping by a derived key is the same tool: group emails by lowercased address, or words by their sorted letters to find anagrams.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does counts.put(x, counts.get(x) + 1) crash the first time x is seen?

2. Why is the HashSet solution to longest consecutive sequence O(n) and not O(n^2)?

3. Why does Majority Element II need a second pass after the vote?

Key takeaways

• Count with merge or getOrDefault; compare counts as ints, not Integer objects.
• O(1) is the average case: buckets, equals, 0.75 load factor, tree bins for heavy collisions.
• Keys must be real signatures with stable equals/hashCode - and never mutated while in the map.
• A HashSet plus "start only at the first value of a run" makes longest consecutive O(n).
• Boyer-Moore voting finds a majority in O(1) space; verify candidates when an answer isn't guaranteed.