Counting and bucket sort

Problem

Many questions only depend on the multiset of items: "are these two words made of the same letters", "which value appears most", "can I build this message from those letters". Order is irrelevant, so sorting does unneeded work and comparing positions does the wrong work. Summarizing the input as counts removes the order and leaves exactly the information needed.

Intuition

A frequency table is a tally sheet: one mark per item, grouped by kind. Two sheets that match describe the same collection no matter how the items were arranged. That is why two anagrams look identical once counted and different when compared letter by letter.

The second idea is that a count can itself be a position. If you want values ordered by how often they appear, you do not need a comparison sort: no value can appear more than n times, so make n + 1 shelves labelled 0 to n, put each value on the shelf matching its count, and read the shelves from the top. That is bucket sort, and it runs in O(n) because it never compares two values.

A different element cancels one vote; when the counter hits zero the next element becomes the candidate.

Mechanics

The frequency table

Build it in one pass: for each item, add one to its entry. In Python, collections.Counter(items) does this. For lowercase letters an array of 26 ints indexed by ord(c) - ord("a") uses constant space. Comparing two tables is a loop over the keys; with an array it is a single list comparison.

Canonical keys for grouping

To group equivalent items, find a value that is identical for equivalent items and different for others, then use it as a dict key. For anagrams there are two choices: the sorted letters (O(L log L) per word of length L) or the tuple of 26 counts (O(L) per word). Either is a canonical form: a unique representative of the equivalence class. The same reasoning groups strings by shifting, numbers by digit multiset, or points by slope.

Boyer-Moore majority voting

Keep one candidate and one counter. For each element: if the counter is zero, make this element the candidate; then add one if the element equals the candidate, else subtract one. Why it works: every decrement cancels one occurrence of the candidate against one different element. If a value occurs more than n/2 times, it outnumbers all other values combined, so cancellation pairs can never use up all its occurrences and it must be the candidate at the end. The converse does not hold: the final candidate is only a possible majority, so a second pass must count it when the problem does not promise one exists. The same argument with k − 1 candidates finds everything above n/k; for n/3 that means two candidates and two counters.

Bucket sort by frequency

After counting, create n + 1 empty lists. Append each value to the list at index equal to its count. Scan the lists from index n down to 1 and collect values until you have k. Counting is O(n), filling the buckets is O(d) for d distinct values and the scan is O(n), so the whole thing is O(n), compared with O(n log n) for sorting by count and O(n log k) for a heap.

The shelf index is the count, so reading them in order needs no comparisons.

Worked example

Anagram test. Count each letter of "listen" and "silent" and compare.

Every row matches, so they are anagrams. For "rat" and "car" the counts differ for 2 of 4 letters, so they are not.

Grouping. Using sorted letters as the key on ["eat", "tea", "tan", "ate", "nat", "bat"]:

Voting. The trace of the diagram above, as a table. After the last element the candidate is 2; a verifying pass counts 4 occurrences in 7 elements, a majority.

Implementation

from collections import Counter, defaultdict


def is_anagram(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)


def can_construct(note, magazine):             # spend counts, fail on a negative
    supply = Counter(magazine)
    for letter in note:
        supply[letter] -= 1
        if supply[letter] < 0:
            return False
    return True


def group_anagrams(words):                     # canonical key: 26-count tuple
    groups = defaultdict(list)
    for word in words:
        counts = [0] * 26
        for letter in word:
            counts[ord(letter) - ord("a")] += 1
        groups[tuple(counts)].append(word)     # tuples are hashable, lists are not
    return list(groups.values())


def majority_element(nums):                    # Boyer-Moore, O(1) space
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate                           # verify with a second pass if no majority is guaranteed


def top_k_frequent(nums, k):                   # bucket sort, O(n)
    buckets = [[] for _ in range(len(nums) + 1)]
    for value, count in Counter(nums).items():
        buckets[count].append(value)
    result = []
    for bucket in reversed(buckets):
        result.extend(bucket)
        if len(result) >= k:
            return result[:k]
    return result

Variations and edge cases

• Elements above n/3. Keep two candidates with two counters; when an element matches neither and both counters are non-zero, decrement both. Always verify afterwards, because the survivors are only possible answers.
• Palindrome from letters. Count letters: every even count is usable in full, each odd count contributes its largest even part, and one centre letter may be added if any count was odd.
• Difference of counts. A single Counter with +1 for one string and −1 for the other checks an anagram in one table; it works if every value ends at zero.
• Counting with a sliding window. Sliding-window pages keep a count table for the window and update it as the edges move.
• Edge cases: strings of different lengths (reject immediately), uppercase or non-letter characters breaking a 26-slot array, counts missing from a dict (use .get or Counter), ties in frequency (the problem usually says any order is fine), and skipping the verification pass after Boyer-Moore.

Complexity and tradeoffs

• Time: counting is O(n); anagram checks are O(L); bucket sort for top-k is O(n). Canonical keys cost O(L log L) per word with sorting and O(L) with a count tuple (plus 26 per key to hash).
• Space: a table of d distinct keys is O(d); over a fixed alphabet that is O(1). Boyer-Moore uses O(1) regardless of input. Bucket sort needs O(n) for the shelves.
• Baselines. Sorting both strings is O(L log L) and uses no hash table, which can be the right answer when memory is tight. Top-k by sorting counts is O(d log d), by a heap O(d log k).
• When it fails. Counts discard order, so they cannot answer questions about subarrays or adjacency by themselves; combine them with a window. If frequencies are not bounded by a small number (weighted scores, real-valued keys) the bucket shelves disappear; use a heap.

Problems

The home problems are counting and grouping on letters and values, one voting problem pair and one bucket-sort ranking. The "also uses" list shows window and greedy problems that keep a count table as their state.

Easy

• 169. Majority Element Grind 169 NeetCode 250
  Boyer-Moore voting pairs off different values; a majority element cannot be fully cancelled, so it survives as the candidate.
• 242. Valid Anagram Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Two strings are anagrams exactly when every letter count matches.
• 383. Ransom Note Grind 169
  Count the magazine's letters and spend one per note letter, failing as soon as any count would go negative.
• 409. Longest Palindrome Grind 169
  Use every even count in full and the largest even part of each odd count, then add one centre character if any count was odd.

Medium

• 49. Group Anagrams Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Give every word a canonical key, either its sorted letters or its 26 letter counts, and group words by that key.
• 229. Majority Element II NeetCode 250
  At most two values can occur more than n/3 times, so run Boyer-Moore voting with two candidates and then verify both.
• 347. Top K Frequent Elements Blind 75 NeetCode 150 NeetCode 250
  Count frequencies, then put values into buckets indexed by count and read buckets from highest to lowest until k values are collected.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 997. Find the Town Judge Easy
• 75. Sort Colors Medium
• 424. Longest Repeating Character Replacement Medium
• 438. Find All Anagrams in a String Medium
• 567. Permutation in String Medium
• 692. Top K Frequent Words Medium
• 767. Reorganize String Medium
• 2013. Detect Squares Medium
• 76. Minimum Window Substring Hard

Connections

Everything here builds on the dict and set mechanics of the hash map page. The top-k idea comes back with heaps, where the heap replaces the shelves when counts are unbounded. Sliding-window problems on strings keep a count table of the window, and greedy problems such as rearranging a string reason from the most frequent letter.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: section 8.2 (counting sort) and section 8.4 (bucket sort).
• Boyer and Moore, "MJRTY: a fast majority vote algorithm" (1981); Misra and Gries, "Finding repeated elements", Science of Computer Programming 2 (1982), for the n/k generalization.
• Sedgewick and Wayne, Algorithms: section 5.1 (key-indexed counting).
• Steven Skiena, The Algorithm Design Manual: the section on bucket sort and distribution sorts.
• Python documentation: collections.Counter.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.