Frequency Counting & Bucket Sort

When an array beats a hash map

For problems whose alphabet is known and small, a fixed-size integer array gives O(1) updates with smaller constants and better cache behaviour than a hash map. "Smaller constants" matters when the alphabet is 26 or 128, the array is faster, simpler, and uses less memory than a Python dict.

def is_anagram(s, t):
    if len(s) != len(t): return False
    counts = [0] * 26                        # lowercase ASCII
    for c in s: counts[ord(c) - ord('a')] += 1
    for c in t:
        counts[ord(c) - ord('a')] -= 1
        if counts[ord(c) - ord('a')] < 0: return False
    return True

The early-exit on negative count is the optimisation that makes this strictly better than "build two counters and compare". As soon as t contains a character that s didn't, the negative count is detected and we return immediately.

For Unicode or arbitrary inputs, an array isn't viable, fall back to a hash map. The decision rule: if the alphabet is bounded and small, prefer an array; if it's unbounded or unknown, use a hash map.

Top-K frequent, bucket sort beats heap

"Return the K most frequent elements in an array." The textbook answer uses a min-heap of size K, O(n log k). The bucket-sort approach is O(n) and simpler.

Idea: count frequencies. Then group values by frequency in an array of length n + 1 (any value can appear at most n times). Walk the buckets from highest frequency down, collecting K values.

from collections import Counter

def top_k_frequent(nums, k):
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for val, cnt in freq.items():
        buckets[cnt].append(val)
    out = []
    for i in range(len(buckets) - 1, 0, -1):
        out.extend(buckets[i])
        if len(out) >= k:
            return out[:k]
    return out

Total work: counting (O(n)) + bucket fill (O(distinct)) + bucket walk (O(n)). Net: O(n). Memory: O(n) for the buckets and the counter. Beats heap on time; ties on memory.

The technique generalises to any "top-K by some integer score, where the score is bounded". Frequency is bounded by n; positive scores are bounded by their range. Whenever the score range is comparable to n, bucket sort is the right tool.

Boyer-Moore majority vote

"Given an array where one element appears more than n/2 times, find it." Hash-map approach: O(n) time, O(n) space. Sort: O(n log n). Boyer-Moore: O(n) time, O(1) memory.

def majority_element(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

The intuition is paired-cancellation. Each non-majority element can cancel at most one majority element. Since the majority appears more than n/2 times, after every pairing some majority element survives. The exact algorithm doesn't track pairings explicitly, it just maintains a single candidate with a counter, swapping when the counter drains.

Important caveat: the algorithm assumes a strict majority exists. If you're not sure, run a second pass to verify the candidate's count. Without verification, the algorithm returns whatever happens to win the cancellation game, which could be any frequent element.

Signature-based grouping

"Group anagrams together." The relevant fact for "is X equivalent to Y?" is some canonical form, sort the characters, or use a 26-length count tuple. Hash-map keys can be anything hashable; tuples qualify.

def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = tuple(sorted(s))               # one form of signature
        groups.setdefault(key, []).append(s)
    return list(groups.values())

For lowercase ASCII the count-tuple tuple(counts) is faster than sorting (O(L) vs O(L log L) per word). The technique extends to "group rotations of a string", "group shape-equivalent trees", and many other equivalence-class problems, pick the canonical form, hash on it, group.

Picking the right tool

Where beginners go wrong

• Using a hash map when an array suffices. 26 buckets of int beat Counter on lowercase-ASCII problems. The array isn't a default; it's the right tool for bounded alphabets.
• Forgetting Boyer-Moore's verification step. If a strict majority is not guaranteed, the candidate might be wrong. A second pass to count occurrences is required.
• Sorting to find top-K. Sort + take-first-K is O(n log n). Bucket sort is O(n). Heap is O(n log k). For small K, all three are fine; for large K, bucket sort wins.
• Using a list as a multiset signature. Lists aren't hashable in Python; you can't put one in a dict key. Convert to a tuple.
• Iterating a Counter and assuming order. Python 3.7+ preserves insertion order in dicts, but relying on it for correctness is fragile. If you need ordered iteration by frequency, sort or bucket explicitly.

What to read next

The Seen-So-Far Pattern is the close relative, both rely on hash-map lookups, but for different question shapes. The Sorting & Search module covers bucket sort, counting sort, and the cases where they beat comparison sorts. The Strings module exercises frequency counting on small alphabets in nearly every problem.