Hints — p42 Top K Frequent Elements

Hint 1. Frequency-count first: counter = Counter(nums) → {val: count}. From here, the question becomes “top K by count value.”

Hint 2. Heap version: min-heap of size K with (count, val) tuples. On overflow, heappushpop the smaller. At end, extract values.

heap = []
for val, cnt in counter.items():
    if len(heap) < k: heappush(heap, (cnt, val))
    elif cnt > heap[0][0]: heappushpop(heap, (cnt, val))
return [val for cnt, val in heap]

O(n log K).

Hint 3. Can we beat O(n log K)? YES — counts are bounded: 1 ≤ count ≤ n. So make a buckets array of size n + 1 indexed by frequency. Sweep from high to low collecting elements until you have K.

Hint 4. Bucket sort skeleton:

buckets = [[] for _ in range(len(nums) + 1)]
for val, cnt in counter.items(): buckets[cnt].append(val)
result = []
for c in range(len(buckets) - 1, 0, -1):
    for val in buckets[c]:
        result.append(val)
        if len(result) == k: return result

O(n) — total work proportional to #distinct + sweep.

Hint 5. LC 692 tie-break (lex order): use composite key (-count, word) so smaller-count or lex-larger word “loses”. Direct sort with this key, or push (-cnt, word) into a size-K min-heap then carefully reverse.

If still stuck: see solution.py.