37. Top-K Frequent Intents

Problem

A reporting job scans a stream of intent labels, one per handled conversation (e.g. "billing", "refund", "account"), and needs the k most common intents to surface on a dashboard. Given the full list of intent labels and k, return the k intents that occur most often, most frequent first, without fully sorting every distinct intent by frequency.

Ties in frequency are broken alphabetically ascending. The point of the problem is to avoid an O(m log m) sort over all m distinct intents when you only need the top k of them.

Source: src/37_top_k_frequent_intents.py

def top_k_frequent(intents: list[str], k: int) -> list[str]:

>>> top_k_frequent(["billing","billing","refund","account","refund","billing"], k=2)
['billing', 'refund']
>>> top_k_frequent(["b","a","a","b","c"], k=2)
['a', 'b']

Step-by-Step Approach

1. Count occurrences of every intent label in a single O(n) pass, using a hash map (e.g. collections.Counter).
2. Recognize that once you have counts, the remaining question is "select the top k by count" over the m distinct keys — a classic top-k selection problem, not a full sort.
3. Use a heap-based selection (heapq.nlargest, or an equivalent manual min-heap of size k) over the distinct intents rather than sorting all of them.
4. Define a sort key that puts higher frequency first, and among equal frequencies, breaks ties alphabetically ascending — for example (count, tuple(-ord(ch) for ch in word)), so that within a tie, "a" and "b" order lexicographically rather than by insertion order.
5. Handle k = 0 (return an empty list) and k larger than the number of distinct intents (return every distinct intent, still ordered by frequency then alphabetically) as edge cases.
6. Return the selected intents as a list, most frequent first.

The key insight is that counting is unavoidable at O(n), but selecting the top k of m distinct items only needs O(m log k) via a heap, which beats an O(m log m) full sort whenever k is much smaller than the number of distinct items.

Reference solution

import heapq
from collections import Counter


def top_k_frequent(intents: list[str], k: int) -> list[str]:
    # count once O(n), then heapq.nlargest over the m distinct intents is O(m log k);
    # key negates each char's ord so alphabetically-earlier words win frequency ties
    # distinct intent -> count, one O(n) pass
    counts = Counter(intents)
    # tuple key: count first, then negated ord() to break ties alphabetically
    return heapq.nlargest(k, counts.keys(), key=lambda w: (counts[w], tuple(-ord(ch) for ch in w)))

Key Functions & Tricks

• collections.Counter(intents) — counts each distinct item in one O(n) pass.
• heapq.nlargest(k, iterable, key=None) — top-k via bounded heap, O(m log k) not O(m log m).
• counts.keys() — distinct intents, the candidate pool passed to nlargest.
• key=lambda w: (counts[w], ...) — tuple key compares lexicographically, count first then tie-break.
• ord(ch) — character's Unicode code point, used to build a comparable tie-break value.
• tuple(-ord(ch) for ch in w) — negated code points turn "alphabetically first" into "numerically largest".

How to Recognize This Pattern